Seminars and Colloquia by Series

Lecture series on the disjoint paths algorithm

Series
Graph Theory Seminar
Time
Monday, February 7, 2011 - 14:05 for 1 hour (actually 50 minutes)
Location
Skiles 168
Speaker
Paul WollanGT, Math and University of Rome
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.

Decomposing an infinite matroid into its 3-connected minors

Series
Graph Theory Seminar
Time
Thursday, February 3, 2011 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Luke PostleMath, GT
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.

Lecture series on the disjoint paths algorithm

Series
Graph Theory Seminar
Time
Monday, January 31, 2011 - 14:05 for 1 hour (actually 50 minutes)
Location
Skiles 168
Speaker
Paul WollanGT, Math and University of Rome
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.

Traveling Salesman Problems

Series
Graph Theory Seminar
Time
Thursday, December 2, 2010 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 114
Speaker
Bill CookISyE, GT
We discuss open research questions surrounding the traveling salesman problem. A focus will be on topics having potential impact on the computational solution of large-scale problem instances.

Kelly width

Series
Graph Theory Seminar
Time
Thursday, November 11, 2010 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 114
Speaker
Nishad KothariCS, GT
Tree-width is a well-known metric on undirected graphs that measures how tree-like a graph is and gives a notion of graph decomposition that proves useful in fixed-parameter tractable (FPT) algorithm development. In the directed setting, many similar notions have been proposed - none of which has been accepted widely as a natural generalization of tree-width. Among the many suggested equivalent parameters were the "directed tree-width" by Johnson et al, and DAG-width by Berwanger et al and Odbrzalek. In this talk, I will present a recent paper by Hunter and Kreutzer, that defines another such directed width parameter, celled "kelly-width". I will discuss the equivalent complexity measures for graphs such as elimination orderings, k-trees and cops and robber games and study their natural generalizations to digraphs. I will discuss its usefulness by discussing potential applications including polynomial-time algorithms for NP-complete problems on graphs of bounded Kelly-width (FPT). I will also briefly discuss our work in progress (joint with Shiva Kintali) towards designing an approximation algorithm for Kelly Width.

Introduction to infinite matroids

Series
Graph Theory Seminar
Time
Thursday, September 30, 2010 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 114
Speaker
Luke PostleMath, GT
Rota asked in the 1960's how one might construct an axiom system for infinite matroids. Among the many suggested answers were the B-matroids of Higgs. In 1978, Oxley proved that any infinite matroid system with the notions of duality and minors must be equivalent to B-matroids. He also provided a simpler mixed basis-independence axiom system for B-matroids, as opposed to the complicated closure system developed by Higgs. In this talk, we examine a recent paper of Bruhn et al that gives independence, basis, circuit, rank, and closure axiom systems for B-matroids. We will also discuss some open problems for infinite matroids.

Choosability of planar graphs

Series
Graph Theory Seminar
Time
Thursday, September 23, 2010 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 114
Speaker
Zdenek DvorakCharles University, Prague, Czech Republic
A graph is k-choosable if it can be properly colored from any assignment of lists of colors of length at least k to its vertices. A well-known results of Thomassen state that every planar graph is 5-choosable and every planar graph of girth 5 is 3-choosable. These results are tight, as shown by constructions of Voigt. We review some new results in this area, concerning 3-choosability of planar graphs with constraints on triangles and 4-cycles.

Geometry of lattices associated to a given graph

Series
Graph Theory Seminar
Time
Thursday, September 16, 2010 - 11:05 for 1 hour (actually 50 minutes)
Location
Skiles 114
Speaker
Omid AminiCNRS-École Normale Supérieure
We present some geometric properties of the Laplacian lattice and the lattice of integer flows of a given graph and discuss some applications and open problems.

The number of vertices in a 6-critical graph is linear in its genus

Series
Graph Theory Seminar
Time
Thursday, September 2, 2010 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 114
Speaker
Luke PostleMath, GT
A deep theorem of Thomassen shows that for any surface there are only finitely many 6-critical graphs that embed on that surface. We give a shorter self-contained proof that for any 6-critical graph G that embeds on a surface of genus g, that |V(G)| is at most linear in g. Joint work with Robin Thomas.

A shorter proof for the disjoint paths algorithm

Series
Graph Theory Seminar
Time
Friday, June 11, 2010 - 16:20 for 1 hour (actually 50 minutes)
Location
Skiles 254
Speaker
Paul WollanThe Sapienza University of Rome
The theory of graph minors developed by Robertson and Seymour is perhaps one of the deepest developments in graph theory. The theory is developed in a sequence of 23 papers, appearing from the 80's through today. The major algorithmic application of the work is a polynomial time algorithm for the k disjoint paths problem when k is fixed. The algorithm is relatively simple to state - however the proof uses the full power of the Robertson Seymour theory, and consequently runs approximately 400-500 pages. We will discuss a new proof of correctness that dramatically simplifies this result, eliminating many of the technicalities of the original proof. This is joint work with Ken-ichi Kawarabayashi.

Pages