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:20240312T163000
DTEND;TZID=Asia/Seoul:20240312T173000
DTSTAMP:20260418T150606
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
END:VCALENDAR