Seminar: Matchings, Perfect Matchings, and the Lovasz-Plummer Conjeture

Dr. Andrew King (Simon Fraser University)

Friday, February 8, 2013, 10:00 a.m., EV 3.309

Abstract

A matching in a graph is simply a set of edges, no two of which share an endpoint. Matchings are fundamental not only to graph theory, but to computer science in general, as they can be used to model a broad class of problems in which we must pair up certain objects according to a set of basic constraints. In this talk I will discuss perfect matchings in bipartite graphs -- it is immediately clear how such objects model problems in which we must match objects in one set to objects in another set, with nothing excluded, for example when we need to match network traffic requests to servers. But these perfect matchings also have less obvious applications in areas such as complexity theory and mathematical chemistry.

In the 1970s, Lovász and Plummer conjectured that the number of perfect matchings in a bridgeless cubic graph is exponential compared to its size. This was proven by Voorhoeve for bipartite graphs and by Chudnovsky and Seymour for planar graphs. I will present an outright proof of the conjecture that uses elements of both earlier proofs, as well as properties of the perfect matching polytope.

This is joint work with Louis Esperet, Frantisek Kardos, Daniel Kral, and Sergey Norin.

Bio

Andrew King is a PIMS Postdoctoral Fellow working with Pavol Hell and Bojan Mohar at Simon Fraser University. He received his Ph.D. from the School of Computer Science at McGill University under the supervision of Bruce Reed, writing his dissertation on the subject of colouring and decomposing claw-free graphs. Following this he spent two years as an NSERC Postdoctoral Fellow with Maria Chudnovsky at Columbia University's Industrial Engineering and Operations Research Department. His main research interests include graph algorithms, bounding the chromatic number, graph clustering, and structural decomposition.