Georgia Institute of Technology College of Sciences

The k-disjoint paths problem takes as input a graph G and k pairs of vertices (s_1, t_1),..., (s_k, t_k) and determines if there exist internally disjoint paths P_1,..., P_k such that the endpoints of P_i are s_i and t_i for all i=1,2,...,k. While the problem is NP-complete when k is allowed to be part of the input, Robertson and Seymour showed that there exists a polynomial time algorithm for fixed values of k. The existence of such an algorithm is the major algorithmic result of the Graph Minors series. The original proof of Robertson and Seymour relies on the whole theory of graph minors, and consequently is both quite technical and involved. Recent results have dramatically simplified the proof to the point where it is now feasible to present the proof in its entirety. This seminar series will do just that, with the level of detail aimed at a graduate student level.

The graph minor structure theorem of Robertson and Seymour gives anapproximate characterization of which graphs do not contain some fixedgraph H as a minor. The theorem has found numerous applications,including Robertson and Seymour's proof of the polynomial timealgorithm for the disjoint paths problem as well as the proof ofWagner's conjecture that graphs are well quasi-ordered under the minorrelation. Unfortunately, the proof of the structure theorem isextremely long and technical. We will discuss a new proof whichgreatly simplifies the argument and makes the result more widelyaccessible. This is joint work with Ken-ichi Kawarabayashi.

All are welcome to discuss professionalism in math, including inviting a speaker, asking questions in talks, dress code at conferences and workshops, and sending polite requests to strangers. Some topics specifically pertaining to women's issues may be discussed. If possible, contact Becca Winarski (rwinarski@math.gatech.edu) if you plan to attend, however, note that everyone is welcome even if you do not respond.

This will be a continuation from last week. We extend the theory of infinite matroids recently developed by Bruhn et al to a well-known classical result in finite matroids while using the theory of connectivity for infinitematroids of Bruhn and Wollan. We prove that every infinite connected matroid M determines a graph-theoretic decomposition tree whose vertices correspond to minors of M that are3-connected, circuits, or cocircuits, and whose edges correspond to 2-separations of M. Tutte and many other authors proved such a decomposition for finite graphs; Cunningham andEdmonds proved this for finite matroids and showed that this decomposition is unique if circuits and cocircuits are also allowed. We do the same for infinite matroids. The knownproofs of these results, which use rank and induction arguments, do not extend to infinite matroids. Our proof avoids such arguments, thus giving a more first principles proof ofthe finite result. Furthermore, we overcome a number of complications arising from the infinite nature of the problem, ranging from the very existence of 2-sums to proving the treeis actually graph-theoretic.