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:20240101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20250408T163000
DTEND;TZID=Asia/Seoul:20250408T173000
DTSTAMP:20260417T014155
CREATED:20250210T063056Z
LAST-MODIFIED:20250331T224202Z
UID:10560-1744129800-1744133400@dimag.ibs.re.kr
SUMMARY:Marcelo Garlet Milani\, Cycles of Well-Linked Sets and an Elementary Bound for the Directed Grid Theorem
DESCRIPTION:In 2015\, Kawarabayashi and Kreutzer proved the directed grid theorem. The theorem states the existence of a function f such that every digraph of directed tree-width f(k) contains a cylindrical grid of order k as a butterfly minor\, but the given function grows non-elementarily with the size of the grid minor. \nWe present an alternative proof of the directed grid theorem\, first proven by Kawarabayashi and Kreutzer in 2015\, which is conceptually much simpler\, more modular in its composition and also improves the upper bound for the function f to a power tower of height 22. \nOur proof is inspired by the breakthrough result of Chekuri and Chuzhoy\, who proved a polynomial bound for the excluded grid theorem for undirected graphs. We translate a key concept of their proof to directed graphs by introducing cycles of well-linked sets (CWS)\, and show that any digraph of high directed tree-width contains a large CWS\, which in turn contains a large cylindrical grid. \nThis is joint work with Meike Hatzel\, Stephan Kreutzer and Irene Muzi.
URL:https://dimag.ibs.re.kr/event/2025-04-08/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR