Loading Events

« All Events

  • This event has passed.

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

March 26 Tuesday @ 4:30 PM - 5:30 PM KST

Room B332, IBS (기초과학연구원)


Evangelos Protopapas
University of Montpellier

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.


March 26 Tuesday
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:


Room B332
IBS (기초과학연구원) + Google Map


Sang-il Oum (엄상일)
View Organizer Website
IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.