Friday, March 18, 2011
3:30 pm, MC 5158

Sergey Norin
Princeton University

Exponentially many perfect matchings in cubic graphs

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.