Proving the Lovász-Plummer Conjecture

Andrew King

Department of Mathematics and Computer Science, Simon Fraser University, Vancouver, Victoria, Canada

Department of Mathematics and Computer Science, Simon Fraser University, Vancouver, Victoria, Canada

2012/02/08 Wed 4PM-5PM

In the 1970s, Lovász and Plummer conjectured that every cubic bridgeless graph has exponentially many perfect matchings. This 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.

(Joint work with Louis Esperet, František Kardoš, Daniel Král’, and Sergey Norin.)

(Joint work with Louis Esperet, František Kardoš, Daniel Král’, and Sergey Norin.)

Tags: AndrewKing