### Rutgers Discrete Mathematics Seminar

Title: Exponentially many perfect matchings in cubic graphs

Speaker: **Sergey Norin**, Princeton University

Date: Tuesday, February 15, 2011 2:00pm

Location: Hill Center, Room 525, Rutgers University, Busch Campus, Piscataway, NJ

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.