BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.16.2//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:20240312T163000
DTEND;TZID=Asia/Seoul:20240312T173000
DTSTAMP:20260527T002306
CREATED:20240215T014045Z
LAST-MODIFIED:20240707T072526Z
UID:8255-1710261000-1710264600@dimag.ibs.re.kr
SUMMARY:Linda Cook\, On polynomial degree-boundedness
DESCRIPTION:We prove a conjecture of Bonamy\, Bousquet\, Pilipczuk\, Rzążewski\, Thomassé\, and Walczak\, that for every graph $H$\, there is a polynomial $p$ such that for every positive integer $s$\, every graph of average degree at least $p(s)$ contains either $K_{s\,s}$ as a subgraph or contains an induced subdivision of $H$. This improves upon a result of Kühn and Osthus from 2004 who proved it for graphs whose average degree is at least triply exponential in $s$ and a recent result of Du\, Girão\, Hunter\, McCarty and Scott for graphs with average degree at least singly exponential in $s$. \nAs an application\, we prove that the class of graphs that do not contain an induced subdivision of $K_{s\,t}$ is polynomially $\chi$-bounded. In the case of $K_{2\,3}$\, this is the class of theta-free graphs\, and answers a question of Davies. Along the way\, we also answer a recent question of McCarty\, by showing that if $\mathcal{G}$ is a hereditary class of graphs for which there is a polynomial $p$ such that every bipartite $K_{s\,s}$-free graph in $\mathcal{G}$ has average degree at most $p(s)$\, then more generally\, there is a polynomial $p’$ such that every $K_{s\,s}$-free graph in $\mathcal{G}$ has average degree at most $p'(s)$. Our main new tool is an induced variant of the Kővári-Sós-Turán theorem\, which we find to be of independent interest. \nThis is joint work with Romain Bourneuf (ENS de Lyon)\, Matija Bucić (Princeton)\, and James Davies (Cambridge)\,
URL:https://dimag.ibs.re.kr/event/2024-03-12/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20240326T163000
DTEND;TZID=Asia/Seoul:20240326T173000
DTSTAMP:20260527T002306
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