We present a full characterization of the unavoidable induced subgraphs of graphs with large pathwidth. This consists of two results. The first result says that for every forest H, every graph of sufficiently large pathwidth contains either a large complete subgraph, a large complete bipartite induced minor, or an induced minor isomorphic to H. The second result describes the unavoidable induced subgraphs of graphs with a large complete bipartite induced minor. We will also try to discuss the proof of the first result with as much detail as time permits. Based on joint work with Maria Chudnovsky and Sophie Spirkl.

A family $\mathcal{F}$ of graphs is said to satisfy the Erdős-Pósa property if there exists a function $f$ such that for every positive integer $k$, every graph $G$ contains either $k$ (vertex-)disjoint subgraphs in $\mathcal{F}$ or a set of at most $f(k)$ vertices intersecting every subgraph of $G$ in $\mathcal{F}$. We characterize the obstructions to the Erdős-Pósa property of $A$-paths in unoriented group-labelled graphs. As a result, we prove that for every finite abelian group $\Gamma$ and for every subset $\Lambda$ of $\Gamma$, the family of $\Gamma$-labelled $A$-paths whose lengths are in $\Lambda$ satisfies the half-integral relaxation of the Erdős-Pósa property. Moreover, we give a characterization of such $\Gamma$ and $\Lambda\subseteq\Gamma$ for which the same family of $A$-paths satisfies the full Erdős-Pósa property. This is joint work with Youngho Yoo.

An induced packing of cycles in a graph is a set of vertex-disjoint cycles such that the graph has no edge between distinct cycles of the set. The classic Erdős-Pósa theorem shows that for every positive integer $k$, every graph contains $k$ vertex-disjoint cycles or a set of $O(k\log k)$ vertices which intersects every cycle of $G$. We generalise this classic Erdős-Pósa theorem to induced packings of cycles of length at least $\ell$ for any integer $\ell$. We show that there exists a function $f(k,\ell)=O(\ell k\log k)$ such that for all positive integers $k$ and $\ell$ with $\ell\geq3$, every graph $G$ contains an induced packing of $k$ cycles of length at least $\ell$ or a set $X$ of at most $f(k,\ell)$ vertices such that the closed neighbourhood of $X$ intersects every cycle of $G$. Furthermore, we extend the result to long cycles containing prescribed vertices. For a graph $G$ and a set $S\subseteq V(G)$, an $S$-cycle in $G$ is a cycle containing a vertex in $S$. We show that for all positive integers $k$ and $\ell$ with $\ell\geq3$, every graph $G$, and every set $S\subseteq V(G)$, $G$ contains an induced packing of $k$ $S$-cycles of length at least $\ell$ or a set $X$ of at most $\ell k^{O(1)}$ vertices such that the closed neighbourhood of $X$ intersects every cycle of $G$. Our proofs are constructive and yield polynomial-time algorithms, for fixed $\ell$, finding either the induced packing of the constrained cycles or the set $X$. This is based on joint works with Pascal Gollin, Tony Huynh, and O-joung Kwon.

The group \( S_n \) of permutations on \([n]=\{1,2,\dots,n\} \) is generated by simple transpositions \( s_i = (i,i+1) \). The length \( \ell(\pi) \) of a permutation \( \pi \) is defined to be the minimum number of generators whose product is \( \pi \). It is well-known that the longest element in \( S_n \) has length \( n(n-1)/2 \). Let \( F_n \) be the semigroup of functions \( f:[n]\to[n] \), which are generated by the simple transpositions \( s_i \) and the function \( t:[n]\to[n] \) given by \( t(1) =t(2) = 1 \) and \( t(i) = i \) for \( i\ge3 \). The length \( \ell(f) \) of a function \( f\in F_n \) is defined to be the minimum number of these generators whose product is \( f \). In this talk, we study the length of longest elements in \( F_n \). We also find a connection with the Slater index of a tournament of the complete graph \( K_n \). This is joint work with Yasuhide Numata.

A replacement action is a function $\mathcal L$ that maps each graph to a collection of subgraphs of smaller size. Given a graph class $\mathcal H$, we consider a general family of graph modification problems, called “$\mathcal L$-Replacement to $\mathcal H$”, where the input is a graph $G$ and the question is whether it is possible to replace some induced subgraph $H_1$ of $G$ on at most $k$ vertices by a graph $H_2$ in ${\mathcal L}(H_1)$ so that the resulting graph belongs to $\mathcal H$. “$\mathcal L$-Replacement to $\mathcal H$” can simulate many graph modification problems including vertex deletion, edge deletion/addition/edition/contraction, vertex identification, subgraph complementation, independent set deletion, (induced) matching deletion/contraction, etc. We prove here that, for any minor-closed graph class $\mathcal H$ and for any action $\mathcal L$ that is hereditary, there is an algorithm that solves “$\mathcal L$-Replacement to $\mathcal H$” in time $2^{{\sf poly}(k)}\cdot |V(G)|^2$, where $\sf poly$ is a polynomial whose degree depends on $\mathcal H$.

A major goal of additive combinatorics is to understand the structures of subsets A of an abelian group G which has a small doubling K = |A+A|/|A|. Freiman’s celebrated theorem first provided a structural characterization of sets with small doubling over the integers, and subsequently Ruzsa in 1999 proved an analog for abelian groups with bounded exponent. Ruzsa further conjectured the correct quantitative dependence on the doubling K in his structural result, which has attracted several interesting developments over the next two decades. I will discuss a complete resolution of (a strengthening of) Ruzsa’s conjecture. Surprisingly, our approach is crucially motivated by purely graph-theoretic insights, where we find that the group structure is superfluous and can be replaced by much more general combinatorial structures. Using this general approach, we also obtain combinatorial and nonabelian generalizations of classical results in additive combinatorics, and solve longstanding open problems around Cayley graphs and random Cayley graphs motivated by Ramsey theory, information theory and computer science. Based on joint work with David Conlon, Jacob Fox and Liana Yepremyan.