A survey of Pfaffian orientations of graphs
- Autores: Robin Thomas
- Localización: Proceedings oh the International Congress of Mathematicians: Madrid, August 22-30,2006 : invited lectures / coord. por Marta Sanz Solé
, Javier Soria de Diego , Juan Luis Varona Malumbres , Joan Verdera , Vol. 3, 2006, ISBN 978-3-03719-022-7, págs. 963-984 - Idioma: inglés
- Enlaces
-
Resumen
An orientation of a graph G is Pfaffian if every even cycle C such that G\V (C) has a perfect matching has an odd number of edges directed in either direction of the cycle.
The significance of Pfaffian orientations is that if a graph has one, then the number of perfect matchings (a.k.a. the dimer problem) can be computed in polynomial time.
The question of which bipartite graphs have Pfaffian orientations is equivalent to many other problems of interest, such as a permanent problem of Pólya, the even directed cycle problem, or the sign-nonsingular matrix problem for square matrices. These problems are now reasonably well-understood. On the other hand, it is not known how to efficiently test if a general graph is Pfaffian, but there are some interesting connections with crossing numbers and signs of edgecolorings of regular graphs.
