Graphs and Matroids Seminar - Amena AssemExport this event to calendar

Tuesday, January 11, 2022 — 3:00 PM EST

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.

S M T W T F S
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
  1. 2022 (79)
    1. June (17)
    2. May (10)
    3. April (12)
    4. March (18)
    5. February (10)
    6. January (13)
  2. 2021 (103)
    1. December (3)
    2. November (7)
    3. October (6)
    4. September (12)
    5. August (6)
    6. July (10)
    7. June (12)
    8. May (7)
    9. April (9)
    10. March (13)
    11. February (8)
    12. January (10)
  3. 2020 (119)
  4. 2019 (167)
  5. 2018 (136)
  6. 2017 (103)
  7. 2016 (137)
  8. 2015 (136)
  9. 2014 (88)
  10. 2013 (48)
  11. 2012 (39)
  12. 2011 (36)
  13. 2010 (40)
  14. 2009 (40)
  15. 2008 (39)
  16. 2007 (15)