BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.16.3//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:20250101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20260506T163000
DTEND;TZID=Asia/Seoul:20260506T173000
DTSTAMP:20260610T141531
CREATED:20260313T150340Z
LAST-MODIFIED:20260403T110615Z
UID:12435-1778085000-1778088600@dimag.ibs.re.kr
SUMMARY:Maximilian Gorsky\, The Disjoint Paths Problem lies in the Oort cloud of algorithms
DESCRIPTION:In this talk we discuss recent work to that establishes that the bounds of the Vital Linkage Function is single-exponential. This has immediate impacts on the complexity of the k-Disjoint Paths Problem\, Minor Checking\, and more generally\, the Folio-Problem. We in fact prove something even stronger: It turns out that it is not in fact the number of terminals (or more generally vertices) that matters in these problems\, but rather their structure within the graph. Concretely\, we show that the Vital Linkage Function is single-exponential only in the bidimensionality of the terminals\, whilst the number of terminals contributes only polynomially. A direct consequence of this is an algorithm for the k-Disjoint Paths Problem running in $f(k)n^2$-time\, where f(k) is singly exponential in k and doubly exponential in the bidimensionality of k. This derives directly from an algorithm for the Folio-problem we give that has an analogous runtime. Notably these are the first algorithms for these problems in which the function f is explicit. In particular\, we give the first explicit bounds for the Vital Linkage Function. \nJoint work with Dario Cavallaro\, Stephan Kreutzer\, Dimitrios Thilikos\, and Sebastian Wiederrecht.
URL:https://dimag.ibs.re.kr/event/2026-05-06/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20260512T163000
DTEND;TZID=Asia/Seoul:20260512T173000
DTSTAMP:20260610T141532
CREATED:20260320T061938Z
LAST-MODIFIED:20260407T022605Z
UID:12453-1778603400-1778607000@dimag.ibs.re.kr
SUMMARY:Benjamin Duhamel\, Excluding a forest induced minor
DESCRIPTION:We give an induced counterpart of the Forest Minor theorem: for any t ≥ 2\, the $K_{t\,t}$-subgraph-free H-induced-minor-free graphs have bounded pathwidth if and only if H belongs to a class F of forests\, which we describe as the induced minors of two (very similar) infinite parameterized families. This constitutes a significant step toward classifying the graphs H for which every weakly sparse H-induced-minor-free class has bounded treewidth. Our work builds on the theory of constellations developed in the Induced Subgraphs and Tree Decompositions series. \nThis is a joint work with É. Bonnet and R. Hickingbotham.
URL:https://dimag.ibs.re.kr/event/2026-05-12/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20260519T163000
DTEND;TZID=Asia/Seoul:20260519T173000
DTSTAMP:20260610T141532
CREATED:20251215T012742Z
LAST-MODIFIED:20260511T073042Z
UID:11990-1779208200-1779211800@dimag.ibs.re.kr
SUMMARY:Xavier Goaoc\, A canonical tree decomposition for order types\, and some applications
DESCRIPTION:We introduce and study a notion of decomposition of planar point sets (or rather of their chirotopes) as trees decorated by smaller chirotopes. This decomposition is based on the concept of mutually avoiding sets (which we rephrase as modules)\, and adapts in some sense the modular decomposition of graphs in the world of chirotopes. The associated tree always exists and is unique up to some appropriate constraints. We also show how to compute the number of triangulations of a chirotope efficiently\, starting from its tree and the (weighted) numbers of triangulations of its parts. \nThis is joint work with Mathilde Bouvel\, Valentin Féray\, and Florent Koechlin.
URL:https://dimag.ibs.re.kr/event/2026-05-19/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20260526T163000
DTEND;TZID=Asia/Seoul:20260526T173000
DTSTAMP:20260610T141532
CREATED:20260112T025344Z
LAST-MODIFIED:20260519T011855Z
UID:12084-1779813000-1779816600@dimag.ibs.re.kr
SUMMARY:Fernanda Rivera Omaña\, Erdős-Pósa theorem for matroids
DESCRIPTION:We will look at an analogue theorem of the classical Erdős-Pósa Theorem. We prove a $GF(q)$-representable matroid analogue of Robertson and Seymour’s theorem that planar graphs have an Erdős-Pósa property. Given a matroid $N$\, we prove that for every matroid $M$ with bounded branch width\, $M$ either contains $r$ skew copies of $N$\, or there is a small perturbation of $M$ that doesn’t contain $N$ as a minor. \nThis is joint work with James Davies and Meike Hatzel.
URL:https://dimag.ibs.re.kr/event/2026-05-26/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR