On March 26, 2024, Evangelos Protopapas from LIRMM gave a talk at the Discrete Math Seminar on characterizing minor-closed classes of graphs satisfying the Erdős-Pósa properties for minors. The title of his talk was “Erdős-Pósa Dualities for Minors“.

## 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 \not\in \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 $\frak{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}$, $\frak{C}_{\mathcal{H}}$ is *finite* and we give a complete characterization of it. In particular, we prove that $|\frak{C}_{\mathcal{H}}| = 2^{\operatorname{poly}(\ell(h))}$, 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.