### Tuesday, July 14

## IP4

Permanents, Pfaffian Orientations, and Even-Directed Circuits

2:00 PM-3:00 PM

*Chair: Carla Savage, North Carolina State University*

*Room: Sidney Smith 2118*

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. The speaker will present a proof of 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 presentation is based on joint work with N. Robertson and P.D. Seymour. The structural characterization was independently obtained by W. McCuaig.)

**Robin Thomas**

*School of Mathematics*

*Georgia Institute of Technology
*

*
*

*
**
*

*MMD, 5/29/98*