Online Talk: Archontia Giannopoulou

Tuesday, Jan 25, 3pm ET (8pm GMT, 9am Wed NZDT)
Archontia Giannopoulou, University of Athens
A Matching Theoretic Flat Wall Theorem

Password: email shaylaredlin ~at~ gmail ~.~ com (The password is the same format as usual, but first instead of last.)
 
Abstract:
One of the key theorems in Graph Minors is the Flat Wall Theorem which asserts the existence of a large wall under certain conditions. In this talk, we discuss about graphs with perfect matchings and their relationship with digraphs. Our main focus is on a matching theoretic analogue of the Flat Wall Theorem for bipartite graphs excluding a fixed matching minor. The tight relationship between structural digraph theory and matching theory that allows us to obtain the aforementioned version of Flat Wall Theorem further allow us to deduce a Flat Wall Theorem for digraphs which substantially differs from a previously established directed variant of this theorem.
 
Joint work with Sebastian Wiederrecht.

Online Talk: Mehtaab Sawhney

Tuesday, Jan 18, 3pm ET (8pm GMT, 9am Wed NZDT)
Mehtaab Sawhney, MIT
Enumerating Matroids and Linear Spaces

 
Abstract:
We show that the number of linear spaces on a set of $n$ points and the number of rank-3 matroids on a ground set of size $n$ are both of the form $(cn+o(n))^{n^2/6}$, where $c=e^{\sqrt 3/2-3}(1+\sqrt 3)/2$. This is the final piece of the puzzle for enumerating fixed-rank matroids at this level of accuracy: there are exact formulas for enumeration of rank-1 and rank-2 matroids, and it was recently proved by van der Hofstad, Pendavingh, and van der Pol that for constant $r\ge 4$ there are $(e^{1-r}n+o(n))^{n^{r-1}/r!}$ rank-$r$ matroids on a ground set of size $n$. In our proof, we introduce a new approach for bounding the number of clique decompositions of a complete graph, using quasirandomness instead of the so-called entropy method that is common in this area.

Online Talk: Amena Assem

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.