Friday, March 18, 2011 3:30 pm
-
4:30 pm
EDT (GMT -04:00)
Exponentially many perfect matchings in cubic graphs
Speaker: | Sergey Norin |
---|---|
Affiliation: | Princeton University |
Room: | Mathematics & Computer Building (MC) 5158 |
Abstract:
A well-known conjecture of Lovasz and Plummer asserts that the number of perfect matchings in 2-edge-connected cubic graph is exponential in the number of vertices. Voorhoeve has shown in 1979 that the conjecture holds for bipartite graphs, and Chudnovsky and Seymour have recently shown that it holds for planar graphs. In general case, however, the best known lower bound has been until now barely super-linear.
In
this
talk
we
sketch
a
proof
of
the
conjecture.
The
main
non-elementary
ingredient
of
the
proof
is
Edmonds'
perfect
matching
polytope
theorem.
This
is
joint
work
with
Louis
Esperet,
Frantisek
Kardos,
Andrew
King
and
Daniel
Kral.