Title: Edge-Disjoint Linkage in Infinite Graphs
| Speaker: | Amena Assem |
| Affiliation: | University of Waterloo |
| Zoom: | http://matroidunion.org/?page_id=2477 or contact Shayla Redlin |
Abstract:
In 1980 Thomassen conjectured that, for odd k, an edge-connectivity of k is enough for a graph to be weakly k-linked, meaning any k pairs of terminals can be linked by k edge-disjoint paths. The best known result to date for finite graphs is from 1991, by Andreas Huck, and assumes an edge-connectivity of k+1 for odd k. In 2016, Ok, Richter, and Thomassen proved that, for odd k, an edge-connectivity of k+2 implies weak k-linkage for 1-ended locally finite graphs. An important auxiliary graph in edge-connectivity proofs is the lifting graph.
In
this
talk
I
will
show
how
to
reduce
the
connectivity
condition
in
the
result
of
Ok,
Richter,
and
Thomassen
to
k+1,
and
then
how
to
generalize
to
arbitrary
infinite
graphs,
not
necessarily
locally
finite,
and
possibly
with
uncountably
many
ends.
I
will
also
prove
an
extension
of
a
result
of
Ok,
Richter,
and
Thomassen
about
characterizing
lifting
graphs,
and
show
that
if
the
k-lifting
graph
of
G
at
s,
L(G,s,k),
has
a
connected
complement,
then
the
graph
G
has
either
a
cycle-like
or
path-like
structure
around
s
with
(k-1)/2
edges
between
any
two
consecutive
blobs.
Finally,
I
will
show
how
this
structure
might
be
used
to
prove
that
the
conjecture
for
finite
graphs
implies
the
conjecture
for
infinite
graphs.