Graphs and Matroids Seminar - Amena Assem

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