 |
 |
 |
 |
 |
 |
 |
 |
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
|
|
|
|
|
|
|
|