Matching width and Pfaffian orientations
by
Sergey Norin
Princeton University
Coauthors: Robin Thomas

Pfaffian orientations have been introduced by Kasteleyn to study the dimer problem. The significance of Pfaffian orientations is that if a graph has one, then the number of perfect matchings in this graph can be computed in polynomial time.

The structure of bipartite graphs that admit a Pfaffian orientation is well understood: They can be constructed from planar graphs and one additional sporadic graph via a certain gluing procedure. In this talk we will discuss possible approaches to extending this structural result to general graphs. In particular, one might try to translate certain results of Robertson and Seymour's graph minor series to be applicable to the study of perfect matchings. This approach leads to a concept of matching width that is analogous to tree width and is especially closely connected to directed tree width.

Date received: April 14, 2008