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:20210101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220330T163000
DTEND;TZID=Asia/Seoul:20220330T173000
DTSTAMP:20260419T132146
CREATED:20220330T073000Z
LAST-MODIFIED:20240707T080136Z
UID:5270-1648657800-1648661400@dimag.ibs.re.kr
SUMMARY:Jean-Florent Raymond\, Long induced paths in minor-closed graph classes and beyond
DESCRIPTION:In 1982 Galvin\, Rival\, and Sands proved that in $K_{t\,t}$-subgraph free graphs (t being fixed)\, the existence of a path of order n guarantees the existence of an induced path of order f(n)\, for some (slowly) increasing function f. The problem of obtaining good lower-bounds for f for specific graph classes was investigated decades later and logarithmic bounds have been obtained for planar graphs (more generally for graphs of bounded genus) and for interval graphs. \nIn this talk I will show that every graph of pathwidth less than k that has a path of order n also has an induced path of order $Ω(n^{1/k})$. I will then explain how this result can be used to prove the two following generalizations: \n\nevery graph of treewidth less than k that has a path of order n contains an induced path of order $Ω((\log n)^{1/k})$;\nfor every non-trivial graph class that is closed under topological minors there is a constant d∈(0\,1) such that every graph from this class that has a path of order n contains an induced path of order $Ω((\log n)^d)$.\n\nJoint work with Claire Hilaire.
URL:https://dimag.ibs.re.kr/event/2022-03-30/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
END:VCALENDAR