Robin Thomas
School of Mathematics
Georgia Institute of Technology
Atlanta, GA 30332
Quarta-feira, 1 de abril de 1998, 16 horas
Sala 259, Bloco A, IME-USP
Abstract: In the first part of the course we will discuss tree-decompositions of graphs. A graph G has tree-width at most k if it is a subgraph of a chordal graph H with no complete subgraph on k+2 vertices. The cliques of H form a tree-structure, giving rise to a tree-decomposition of G. Tree-decompositions of graphs play an important role in graph structure theory, in the theory of algorithms and in practical computation. We shall survey all of these aspects. In particular, we will discuss a certain cops-and-robbers game, leading to a min-max theorem for tree-width, tree-width and algorithms, some aspects of practical computation using tree-width, variations of tree-width such as branch-width and path-width, and excluded minor theorems. The latter will serve as a motivation for the second part of the course.
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 shall prove their equivalence, and mention relation to matching decomposition theory developed by Lovasz and Plummer. We shall then prove a theorem of Little that characterizes the infeasible instances of those problems. Unfortunately, Little's theorem does not seem to imply a polynomial-time algorithm.
Finally, we shall outline a solution to the above problems, obtained in joint work with Neil Robertson and P.D. Seymour, and independently by W. McCuaig. The solution is based on a structural characterization of the feasible instances, and 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.