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.)