Tuesday, Jan 11, 3pm ET (8pm GMT, 9am Wed NZDT)
Amena Assem, University of Waterloo
Edge-Disjoint Linkage in Infinite Graphs

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, will show how this structure might be used to prove that the conjecture for finite graphs implies the conjecture for infinite graphs.