Permanents, Pfaffian orientations, and even directed circuits

                             Robin Thomas
                         School of Mathematics
                     Georgia Institute of Technology
                           Atlanta, GA 30332

   Given an n by n 0-1 matrix A, when can some of the 1's be changed to
-1's in such a way that the permament of A equals the determinant of the
modified matrix? When does a real n by n matrix A have the property that
every real matrix B with the same sign pattern (that is, the corresponding
entries either have the same sign, or are both zero) is non-singular?
When is a hypergraph with n vertices and n hyperedges minimally non-bipartite?
When does a bipartite graph have a "Pfaffian orientation"? Given a digraph,
does it have no directed circuit of even length? Given a digraph, does it have
a subdivision with no even directed circuit?

  It is known that all the above problems are equivalent. We prove a
structural characterization of the feasible instances, which implies a
polynomial-time algorithm to solve all of the above problems. The structural
characterization says, roughly speaking, that a bipartite graph has a
Pfaffian orientation if and only if it can be obtained by piecing together
(in a specified way) planar bipartite graphs and one sporadic non-planar
bipartite graph.

  This is joint work with Neil Robertson and P.D. Seymour. The structural
characterization was independently obtained by W. McCuaig.