For any infinite set of graphs, one of them is a minor of another (a
theorem of Neil Robertson and the speaker). The same is not true if we
use induced subgraphs instead of minors, but S. B. Rao conjectured in
about 1980 that it is true for a tweaking of the induced subgraph
relation. Let us say $G$ ``Rao-contains'' $H$ if there is a graph $G'$
with vertex set $V(G)$ and with the same vertex-degrees as $G$, such that
$G'$ contains $H$ as an induced subgraph. Rao conjectured, and we have
now proved, that in any infinite set of graphs one of them Rao-contains another.
The problem turns out to be related to ordering digraphs by immersion
(vertices are mapped to vertices, and edges to edge-disjoint directed
paths). There exist infinite sets of digraphs such that none of them is
immersed in another, but for digraphs of some special types (for instance,
tournaments) there are no such infinite sets, and we need this fact to prove
Rao's conjecture.
The proof method uses digraph "cutwidth". Another application of cutwidth,
joint with Alexandra Fradkin, is a solution to the $k$ edge-disjoint paths
problem for tournaments. For fixed $k$, we give a polynomial time
algorithm that, with input $k$ pairs of vertices $s_i,t_i (1\le i\le k)$ of a
tournament, decides whether there exist $k$ paths from $s_i$ to
$t_i (1\le i\le k)$, pairwise edge-disjoint.
We sketch all this material.
Joint with Maria Chudnovsky, Columbia
Copyright. All Rights Reserved.