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

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.

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.

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.

Another successful open problem session! 🙂 Thank you to everyone who attended and a special thank you to our presenters. The slides are posted below.

Date: Tuesday, December 14
Time: 1:30-4:00pm EST (6:30-9:00pm GMT, 7:30-10:00am Wed NZDT)

Schedule:
Session 1: 1:30-2:30pm EST
Session 2: 3:00-4:00pm EST
Social Time: 4:00pm EST – ??

Format:
In each session, several open problems will be presented. For each problem, we’ll have ~5 minutes for the presentation followed by ~5 minutes for discussion. There may be time at the end of each session for more discussion or unplanned open problem contributions.

Session 1:
1. Nathan Bowler – slides
2. Rose McCarty – slides
3. James Davies – slides
4. Michał Pilipczuk – slides
5. Nicholas Anderson – slides
6. Ben Moore – slides

Session 2:
1. Bruce Richter – slides
2. Michael Wigal – slides
3. Dillon Mayhew – slides
4. Zach Walsh – slides
5. Jorn van der Pol – slides
6. Jim Geelen – slides