The dimension of a poset is the least integer $d$ such that the poset is isomorphic to a subposet of the product of $d$ linear orders. In 1983, Kelly constructed planar posets of arbitrarily large dimension. Crucially, the posets in his construction involve large standard examples, the canonical structure preventing a poset from having small dimension. Kelly’s construction inspired one of the most challenging questions in dimension theory: are large standard examples unavoidable in planar posets of large dimension? We answer the question affirmatively by proving that every $d$-dimensional planar poset contains a standard example of order $\Omega(d)$. More generally, we prove that every poset from Kelly’s construction appears in every poset with a planar cover graph of sufficiently large dimension. joint work with Heather Smith Blake, Jędrzej Hodor, Piotr Micek, and William T. Trotter.

Since the proof of the graph minor structure theorem by Robertson and Seymour in 2004, its underlying ideas have found applications in a much broader range of settings than their original context. They have driven profound progress in areas such as vertex minors, pivot minors, matroids, directed graphs, and 2-dimensional simplicial complexes. In this talk, I will present three open problems related to this development, each requiring some background.

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.