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:20200101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210818T170000
DTEND;TZID=Asia/Seoul:20210818T180000
DTSTAMP:20260420T024018
CREATED:20210818T080000Z
LAST-MODIFIED:20240705T182104Z
UID:4353-1629306000-1629309600@dimag.ibs.re.kr
SUMMARY:Petr Hliněný\, Twin-width is linear in the poset width
DESCRIPTION:Twin-width is a new parameter informally measuring how diverse are the neighbourhoods of the graph vertices\, and it extends also to other binary relational structures\, e.g. to digraphs and posets. It was introduced quite recently\, in 2020 by Bonnet\, Kim\, Thomassé\, and Watrigant. One of the core results of these authors is that FO model checking on graph classes of bounded twin-width is in FPT. With that result\, they also claimed that posets of bounded width have bounded twin-width\, thus capturing a prior result on FO model checking of posets of bounded width in FPT. However\, their translation from poset width to twin-width was indirect and giving only a very loose double-exponential bound. \nWe prove that posets of width d have twin-width at most 9d with a direct and elementary argument\, and show that this bound is tight up to a constant factor. Specifically\, for posets of width 2\, we prove that in the worst case their twin-width is also equal to 2. These two theoretical results are complemented with straightforward algorithms to construct the respective contraction sequence for a given poset. \n(Joint work with my student Jakub Balaban who obtained the main ideas in his bachelor thesis.)
URL:https://dimag.ibs.re.kr/event/2021-08-18/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
END:VCALENDAR