Tutte seminar - Paul Seymour

Well-quasi-ordering tournaments and Rao's degree-sequence conjecture

Abstract:

Rao conjectured about 1980 that in every infinite set of degree sequences (of graphs), there are two degree sequences with graphs one of which is an induced subgraph of the other. In the last month or so we seem to have found a proof, and we sketch the main ideas. 
The problem turns out to be related to ordering digraphs by immersion (vertices are mapped to vertices, and edges to edge-disjoint directed paths). Immersion is not a well-quasi-order for the set of all digraphs, but for certain restricted sets (for instance, the set of tournaments) we prove it is a well-quasi-order. 
The connection between Rao's conjecture and tournament immersion is as follows. One key lemma reduces Rao's conjecture to proving the same assertion for degree sequences of split graphs (a split graph is a graph whose vertex set is the union of a clique and a stable set); and to handle split graphs it helps to encode the split graph as a directed complete bipartite graph, and to replace Rao's containment relation with immersion.

Joint work with Maria Chudnovsky (Columbia University).