Online Talk: O-joung Kwon

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.

 

Online Talk: Ahmad Abdi

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.

Online Talk: Sang-il Oum

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.

Online Talk: Louis Esperet

Tuesday, March 1, 11am ET (4pm GMT, 5am Wed NZDT)
Louis Esperet, G-SCOP Laboratory (CNRS, Grenoble)
Packing and covering balls in planar graphs

 
Abstract:
The set of all vertices at distance at most $r$ from a vertex $v$ in a graph $G$ is called an $r$-ball. We prove that the minimum number of vertices hitting all $r$-balls in a planar graph $G$ is at most a constant (independent of $r$) times the maximum number of vertex-disjoint $r$-balls in $G$. This was conjectured by Estellon, Chepoi and Vaxès in 2007. Our result holds more generally for any proper minor-closed class, and for systems of balls of arbitrary (and possibly distinct) radii.
 
Joint work with N. Bousquet, W. Cames van Batenburg, G. Joret, W. Lochet, C. Muller, and F. Pirot.