Wednesday, July 16, 2014 3:30 pm
-
3:30 pm
EDT (GMT -04:00)
Pfaffian Bipartite Graphs
| Speaker: | Nishad Kothari |
|---|---|
| Affiliation: | University of Waterloo |
| Room: | Mathematics 3 (M3) 2134 |
Abstract:
A
graph
is
Pfaffian
if
it
admits
a
Pfaffian
orientation.
Little
(1975)
showed
that
a
bipartite
graph
is
Pfaffian
if
and
only
if
it
does
not
"contain"
$K_{3,3}$.
This
implies
that
the
problem
of
deciding
whether
a
bipartite
graph
is
Pfaffian
is
in
co-NP.
Around
1999,
Robertson,
Seymour
and
Thomas,
and
independently
McCuaig,
showed
that,
for
bipartite
graphs,
this
problem
is
in
P
(i.e.
poly-time
solvable).
I
will
sketch
a
proof
of
Little's
theorem
given
by
Carvalho,
Lucchesi
and
Murty.
Towards
the
end,
I
will
discuss
how
our
on-going
work
has
connections
to
Pfaffian
orientations.