Abstract of Colloquium talk at Math Department of WVU, October 24, 1996

Professor Robin Thomas

Georgia Institute of Technology

Even circuits in directed graphs

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 bipartite? When does a bipartite graph have a "Pfaffian orientation"?

All of the above problems are equivalent to the even directed circuit problem: Given a directed graph, does it have a directed circuit of even length? We solve this problem by giving a structural characterization of directed graphs such that some subdivision does not have an even directed circuit. The characterization implies a polynomial-time algorithm to solve all the problems mentioned.

This is joint work with Neil Robertson and P.D. Seymour. The talk will be aimed at a general mathematical audience.