Tuesday, March 29, 3pm ET (8pm GMT, 8am Wed NZDT)
Zishen Qu, University of Waterloo
Minimal induced subgraphs of two classes of 2-connected non-Hamiltonian graphs

Abstract:

Finding sufficient conditions for a class of graphs to be Hamiltonian is an old problem, with a wide variety of conditions such as Dirac’s degree condition and Whitney’s theorem on 4-connected planar triangulations. We discuss some past results on sufficient conditions for Hamiltonicity involving the exclusion of fixed induced subgraphs, and some properties of the graphs involved in such results. In 1981 Duffus, Gould, and Jacobson showed that any connected graph that does not contain a claw or a net as an induced subgraph has a Hamiltonian path. We aim to find an analogous result for Hamiltonian cycles. In particular, we would like to find a set of graphs $S$ which are 2-connected, non-Hamiltonian, and every proper 2-connected induced subgraph is Hamiltonian such that every 2-connected $S$-free graph is Hamiltonian. In joint work with Joseph Cheriyan, Sepehr Hajebi, and Sophie Spirkl, we show that the classes of 2-connected split graphs and 2-connected triangle-free graphs can be characterised in this fashion.

Tuesday, March 22, 5pm ET (*9pm* GMT, *10am* Wed NZDT)
O-joung Kwon, Hanyang University
Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond)

Abstract:

In a reduction sequence of a graph, vertices are successively identified until the graph has one vertex. At each step, when identifying $u$ and $v$, each edge incident to exactly one of $u$ and $v$ is coloured red. Bonnet, Kim, Thomassé and Watrigant [J. ACM 2022] defined the twin-width of a graph $G$ to be the minimum integer $k$ such that there is a reduction sequence of $G$ in which every red graph has maximum degree at most $k$. For any graph parameter $f$, we define the reduced $f$ of a graph $G$ to be the minimum integer $k$ such that there is a reduction sequence of $G$ in which every red graph has $f$ at most $k$. Our focus is on graph classes with bounded reduced bandwidth, which implies and is stronger than bounded twin-width (reduced maximum degree). We show that every proper minor-closed class has bounded reduced bandwidth, which is qualitatively stronger than an analogous result of Bonnet et al. for bounded twin-width. In many instances, we also make quantitative improvements. Furthermore, we separate twin-width and reduced bandwidth by showing that any infinite class of expanders excluding a fixed complete bipartite subgraph has unbounded reduced bandwidth, while there are bounded-degree expanders with twin-width at most 6. This is joint work with Édouard Bonnet and David Wood.

Tuesday, March 15, 3pm ET (*7pm* GMT, *8am* Wed NZDT)
Ahmad Abdi, LSE
On packing dijoins in digraphs and weighted digraphs

Abstract:

Let $D=(V,A)$ be a digraph. A dicut is the set of arcs in a cut where all the arcs cross in the same direction, and a dijoin is a set of arcs whose contraction makes $D$ strongly connected. It is known that every dicut and dijoin intersect. Suppose every dicut has size at least $k$.

Woodall’s Conjecture, an important open question in Combinatorial Optimization, states that there exist $k$ pairwise disjoint dijoins. We make a step towards resolving this conjecture by proving that $A$ can be decomposed into two sets $A_1$ and $A_2$, where $A_1$ is a dijoin, and $A_2$ intersects every dicut in at least $k-1$ arcs. We prove this by a Decompose, Lift, and Reduce (DLR) procedure, in which $D$ is turned into a sink-regular $(k,k+1)$-bipartite digraph. From there, by an application of Matroid Optimization tools, we prove the result.

The DLR procedure works more generally for weighted digraphs, and exposes an intriguing number-theoretic aspect of Woodall’s Conjecture. In fact, under natural number-theoretic conditions, Woodall’s Conjecture and a weighted extension of it are true. By pushing the barrier here, we expose strong base orderability as a key notion for tackling Woodall’s Conjecture.

Based on joint work with Gerard Cornuejols and Michael Zlatin.

Tuesday, March 8, **4pm ET** (9pm GMT, 10am Wed NZDT)
Sang-il Oum, Institute for Basic Science / KAIST
Obstructions for matroids of path-width at most $k$ and graphs of linear rank-width at most $k$

Abstract:

Every minor-closed class of matroids of bounded branch-width can be characterized by a minimal list of excluded minors, but unlike graphs, this list could be infinite in general. However, for each fixed finite field $\mathbb F$, the list contains only finitely many $\mathbb F$-representable matroids, due to the well-quasi-ordering of $\mathbb F$-representable matroids of bounded branch-width under taking matroid minors [J. F. Geelen, A. M. H. Gerards, and G. Whittle (2002)]. But this proof is non-constructive and does not provide any algorithm for computing these $\mathbb F$-representable excluded minors in general.

We consider the class of matroids of path-width at most $k$ for fixed $k$. We prove that for a finite field $\mathbb F$, every $\mathbb F$-representable excluded minor for the class of matroids of path-width at most $k$ has at most $2^{|\mathbb{F}|^{O(k^2)}}$ elements. We can therefore compute, for any integer $k$ and a fixed finite field $\mathbb F$, the set of $\mathbb F$-representable excluded minors for the class of matroids of path-width $k$, and this gives as a corollary a polynomial-time algorithm for checking whether the path-width of an $\mathbb F$-represented matroid is at most $k$. We also prove that every excluded pivot-minor for the class of graphs having linear rank-width at most $k$ has at most $2^{2^{O(k^2)}}$ vertices, which also results in a similar algorithmic consequence for linear rank-width of graphs.

This is joint work with Mamadou M. Kanté, Eun Jung Kim, and O-joung Kwon.