Tutorial by Robin
Thomas on Pfaffian Orientations of Graphs
Topics to be covered: Edmonds'
matching theorem, the linear hull of perfect
matchings, the matching structure:
decomposition into bricks and braces, the matching lattice, Pfaffian
orientations and their use, Pfaffian orientations of bipartite graphs,
Polya's permanent problem, the even directed cycle
problem, sign-nonsingular matrices, applications in economics. Directed
tree-width and digraph structure.
Generating bricks, Pfaffian orientations of bricks, relation to
parity of crossing numbers and signs of edge-colorings, linear
combinations of Pfaffians.
Matching width and its relation to directed tree-width.
Here are slides
for my talk the International Congress of Mathematicians,
Madrid, Spain, August 2006.
References:
R.
Diestel, Graph Theory, 2nd edition
T. Johnson, N. Robertson, P.D. Seymour, and R. Thomas, Directed
tree-width. J. Combin. Theory Ser. B
82 (2001), no. 1, 138--154. An addendum.
L. Lovasz and M. Plummer, Matching theory. Annals of Discrete Math. 29,
North-Holland, Amsterdam (1986).
S. Norine, Drawing
Pfaffian graphs, Proc. 12th Int. Symposium on Graph Drawing.
S. Norine, Pfaffian
graphs, T-joins and crossing numbers, to appear in Combinatorica.
S. Norine, Drawing
4-Pfaffian graphs on the torus, submitted.
S. Norine and R. Thomas, Generating
bricks, J. Combin. Theory Ser. B 97 (2007), 769-817.
S. Norine and R. Thomas, Minimal
bricks, J. Combin. Theory Ser. B 96 (2006), 505-513.
S. Norine and R. Thomas, Pfaffian
labelings and signs of edge-colorings,
to appear in Combinatorica.
S. Norine and R. Thomas, Minimally
non-Pfaffian graphs, submitted.
W. McCuaig, Pólya's permanent problem,
Electron. J. Combin. 11 (2004), no. 1, Research Paper 79, 83
pp. (electronic).
W. McCuaig, Brace generation, J. Graph
Theory 38 (2001), no. 3, 124--169.
N. Robertson, P.D. Seymour and R. Thomas, Permanents,
Pfaffian orientations, and even directed
circuits. Ann. of Math. (2) 150 (1999), no. 3, 929--975.
R. Thomas, A survey
of Pfaffian orientations of graphs, Proceedings of the
International Congress of Mathematicians, Madrid, Spain, 2006.