BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Discrete Mathematics Group
X-ORIGINAL-URL:https://dimag.ibs.re.kr
X-WR-CALDESC:Events for Discrete Mathematics Group
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Seoul
BEGIN:STANDARD
TZOFFSETFROM:+0900
TZOFFSETTO:+0900
TZNAME:KST
DTSTART:20230101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20240326T163000
DTEND;TZID=Asia/Seoul:20240326T173000
DTSTAMP:20260418T150606
CREATED:20240115T052614Z
LAST-MODIFIED:20240707T072512Z
UID:8129-1711470600-1711474200@dimag.ibs.re.kr
SUMMARY:Evangelos Protopapas\, Erdős-Pósa Dualities for Minors
DESCRIPTION: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. \nThis is joint work with Christophe Paul\, Dimitrios Thilikos\, and Sebastian Wiederrecht.
URL:https://dimag.ibs.re.kr/event/2024-03-26/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR