Evangelos Protopapas, Erdős-Pósa Dualities for Minors

Let $\mathcal{G}$ and $\mathcal{H}$ be minor-closed graphs classes. The class $\mathcal{H}$ has the Erdős-Pósa property in $\mathcal{G}$ if there is a function $f:\mathbb{N}\to \mathbb{N}$ such that every graph $G$ in $\mathcal{G}$ either contains (a packing of) $k$ disjoint copies of some subgraph minimal graph $H\notin \mathcal{H}$ or contains (a covering of) $f(k)$ vertices, whose removal creates a graph in $\mathcal{H}$. A class $\mathcal{G}$ is a minimal EP-counterexample for $\mathcal{H}$ if $\mathcal{H}$ does not have the Erdős-Pósa property in $\mathcal{G}$, however it does have this property for every minor-closed graph class that is properly contained in $\mathcal{G}$. The set ${\mathfrak{C}}_{\mathcal{H}}$ of the subset-minimal EP-counterexamples, for every $\mathcal{H}$, can be seen as a way to consider all possible Erdős-Pósa dualities that can be proven for minor-closed classes. We prove that, for every $\mathcal{H}$, ${\mathfrak{C}}_{\mathcal{H}}$ is finite and we give a complete characterization of it. In particular, we prove that $|{\mathfrak{C}}_{\mathcal{H}}\mathfrak{|}\mathfrak{=}{\mathfrak{2}}^{\mathrm{poly}\mathfrak{(}\ell \mathfrak{(}\mathfrak{h}\mathfrak{)}\mathfrak{)}}$, where $h$ is the maximum size of a minor-obstruction of $\mathcal{H}$ and $\ell (\cdot )$ is the unique linkage function. As a corollary of this, we obtain a constructive proof of Thomas’ conjecture claiming that every minor-closed graph class has the half-integral Erdős-Pósa property in all graphs.

This is joint work with Christophe Paul, Dimitrios Thilikos, and Sebastian Wiederrecht.