
Discrete Mathematics and Optimization Seminar

Oct. 22nd, 2010 MC 320, 4 PM
Perfect matchings in cubic graphs: A proof of the
LovaszPlummer conjecture
Serguei Norine
Princeton University

Abstract: A wellknown conjecture of Lovasz and Plummer asserts that the number
of perfect matchings in 2edgeconnected cubic graphs 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
superlinear.
In this talk we sketch a proof of the conjecture. The main
nonelementary ingredient of the proof is Edmonds' perfect matching
polytope theorem.
This is joint work with Louis Esperet, Frantisek Kardos, Andrew King
and Daniel Kral.



