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.