BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
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:20220613T163000
DTEND;TZID=Asia/Seoul:20220613T173000
DTSTAMP:20260423T070843
CREATED:20220613T073000Z
LAST-MODIFIED:20240707T075724Z
UID:5578-1655137800-1655141400@dimag.ibs.re.kr
SUMMARY:Amadeus Reinald\, Twin-width and forbidden subdivisions
DESCRIPTION:Twin-width is a recently introduced graph parameter based on vertex contraction sequences. On classes of bounded twin-width\, problems expressible in FO logic can be solved in FPT time when provided with a sequence witnessing the bound. Classes of bounded twin-width are very diverse\, notably including bounded rank-width\, $\Omega ( \log (n) )$-subdivisions of graphs of size $n$\, and proper minor closed classes. In this talk\, we look at developing a structural understanding of twin-width in terms of induced subdivisions. \nStructural characterizations of graph parameters have mostly looked at graph minors\, for instance\, bounded tree-width graphs are exactly those forbidding a large wall minor. An analogue in terms of induced subgraphs could be that\, for sparse graphs\, large treewidth implies the existence of an induced subdivision of a large wall. However\, Sintiari and Trotignon have ruled out such a characterization by showing the existence of graphs with arbitrarily large girth avoiding any induced subdivision of a theta ($K_{2\,3}$). Abrishami\, Chudnovsky\, Hajebi and Spirkl have recently shown that such (theta\, triangle)-free classes have nevertheless logarithmic treewidth. \nAfter an introduction to twin-width and its ties to vertex orderings\, we show that theta-free graphs of girth at least 5 have bounded twin-width. \nJoint work with Édouard Bonnet\, Eun Jung Kim\, Stéphan Thomassé and Rémi Watrigant.
URL:https://dimag.ibs.re.kr/event/2022-06-13/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR