Tutte seminar - U.S.R. Murty

Friday, January 6, 2012 3:30 pm - 3:30 pm EST (GMT -05:00)

On minimal non-Pfaffian graphs

Speaker: U.S.R. Murty
Affiliation: University of Waterloo
Room: Mathematics & Computer Building (MC) 5158

Abstract:

Let $G$ be a graph. An even cycle in $G$ is alternating if its edges belong alternately to two different perfect matchings of $G$. An orientation $D$ of $G$ is Pfaffian if, in every alternating cycle of $G$, an odd number of edges are oriented `clock-wisely' (and, consequently, an odd number of edges are oriented `anti-clock-wisely'). 

An amazing fact is that if $D$ is a Pfaffian orientation of $G$, then the determinant of the adjacency matrix of $D$ is the square of the number of perfect matchings of $G$. 

A graph is Pfaffian if it admits a Pfaffian orientation. 

POP (The Pfaffian Orientation Problem): Given a graph $G$, determine whether or not $G$ is Pfaffian. 

Charles Little (1973) showed that, in a certain sense, $K_{3,3}$ is the only minimal non-Pfaffian bipartite graph. 

(Robertson, Seymour and Thomas (1999), and independently McCuaig (2004), showed that, for bipartite graphs, POP is in ${\cal P}$. Their work has applications to many seemingly unrelated problems in algorithmic graph theory.) 

Using a stronger notion of minimality than Little did, we show that every minimal non-Pfaffian non-bipartite graph $G$ must contain two disjoint odd cycles $C_1$ and $C_2$ such that $G-\{V(C_1)\cup V(C_2)\}$ has a perfect matching. This result has an amusing interpretation in terms of Edmonds' description of perfect matching polytopes.



Co-authors:

This talk is based on a joint paper with Marcelo Carvalho and Cláudio Lucchesi which has been accepted for publication in JCT-B.