- Series
- Combinatorics Seminar
- Time
- Friday, November 1, 2024 - 3:15pm for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Evangelos Protopapas – University of Montpellier – vagelis.protopapas@gmail.com
- Organizer
- Tom Kelly

Let $\mathscr{G}$ and $\mathscr{H}$ be minor-closed graphs classes. The class $\mathscr{H}$ has the *Erdős-Pósa property* in $\mathscr{G}$ if there is a function $f : \mathbb{N} \to \mathbb{N}$ such that every graph $G$ in $\mathscr{G}$ either contains (a *packing* of) $k$ disjoint copies of some subgraph minimal graph $H \not\in \mathscr{H}$ or contains (a *covering* of) $f(k)$ vertices, whose removal creates a graph in $\mathscr{H}$. A class $\mathscr{G}$ is a *minimal EP-counterexample* for $\mathscr{H}$ if $\mathscr{H}$ does not have the *Erdős-Pósa property* in $\mathscr{G}$, however it does have this property for every minor-closed graph class that is properly contained in $\mathscr{G}$. The set $\mathfrak{C}_{\mathscr{H}}$ of the subset-minimal EP-counterexamples, for every $\mathscr{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 $\mathscr{H}$, $\mathfrak{C}_{\mathscr{H}}$ is *finite* and we give a complete characterization of it. In particular, we prove that $|\mathfrak{C}_{\mathscr{H}}| = 2^{\mathsf{poly}(\ell(h))}$, where $h$ is the maximum size of a minor-obstruction of $\mathscr{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.