Well-quasi-ordering tournaments and Rao's degree-sequence conjecture
Speaker: | Paul Seymour |
---|---|
Affiliation: | Princeton University |
Room: | Mathematics & Computer Building (MC) 5158 |
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).