Proving the Lovász-Plummer conjecture

Proving the Lovász-Plummer conjecture

-
Andrew King, Columbia University
Fine Hall 224

In the 1970s, Lovász and Plummer conjectured that every cubic bridgeless graph has exponentially many perfect matchings with respect to the number of vertices. The conjecture was proven by Voorhoeve for bipartite graphs and by Chudnovsky and Seymour for planar graphs. In this talk I will describe our proof of the general case, which uses elements of both aforementioned partial results as well as Edmonds' characterization of the perfect matching polytope. This is joint work with Louis Esperet, Frantisek Kardos, Daniel Kral, and Sergey Norin.