|
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).
|