- You are here:
- GT Home
- Home
- News & Events

Series: Graph Theory Seminar

This lecture will conclude the series. In a climactic finish the speaker will prove the Unique Linkage Theorem, thereby completing the proof of correctness of the Disjoint Paths Algorithm.

Series: Graph Theory Seminar

First-Fit is an online algorithm that partitions the elements of a poset
into chains. When presented with a new element x, First-Fit adds x
to the first chain whose elements are all comparable to x. In 2004,
Pemmaraju, Raman, and Varadarajan introduced the Column Construction
Method to prove that when P is an interval order of width w,
First-Fit partitions P into at most 10w chains. This bound was
subsequently improved to 8w by Brightwell, Kierstead, and Trotter, and
independently by Narayanaswamy and Babu.
The poset r+s is the disjoint union of a chain of size r and a chain
of size s. A poset is an interval order if and only if it does not
contain 2+2 as an induced subposet. Bosek, Krawczyk, and Szczypka
proved that if P is an (r+r)-free poset of width w, then First-Fit
partitions P into at most 3rw^2 chains and asked whether the bound
can be improved from O(w^2) to O(w). We answer this question in
the affirmative. By generalizing the Column Construction Method, we
show that if P is an (r+s)-free poset of width w, then First-Fit
partitions P into at most 8(r-1)(s-1)w chains.
This is joint work with Gwena\"el Joret.

Series: Graph Theory Seminar

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.

Series: Graph Theory Seminar

Series: Graph Theory Seminar

Series: Graph Theory Seminar

Series: Graph Theory Seminar

A graph is k-critical if it is not (k-1)-colorable but every proper subgraph is. In 1963, Gallai conjectured that every k-critical graph G of order n has at least (k-1)n/2 + (k-3)(n-k)/(2k-2) edges. The currently best known results were given by Krivelevich for k=4 and 5, and by Kostochka and Stiebitz for k>5. When k=4, Krivelevich's bound is 11n/7, and the bound in Gallai's conjecture is 5n/3 -2/3. Recently, Farzad and Molloy proved Gallai's conjecture for k=4 under the extra condition that the subgraph induced by veritces of degree three is connected. We will review the proof given by Krivelevich, and the proof given by Farzad and Molloy in the seminar.

Series: Graph Theory Seminar

Series: Graph Theory Seminar

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.

Series: Graph Theory Seminar