BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.17.1//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:20260804T163000
DTEND;TZID=Asia/Seoul:20260804T173000
DTSTAMP:20260725T124528Z
CREATED:20260617T111737Z
LAST-MODIFIED:20260725T124528Z
UID:12779-1785861000-1785864600@dimag.ibs.re.kr
SUMMARY:Tomohiro Koana\, A Single-Exponential FPT Algorithm for 2-Vertex-Connectivity Augmentation
DESCRIPTION:We study restricted-link augmentation to 2-vertex-connectivity. An instance consists of a graph $G$\, possibly disconnected\, a set $L$ of admissible links on its vertices\, integer link costs in $\{1\, \ldots\, W\}$\, and an integer $k$; the task is to add at most $k$ links of minimum total cost so that the resulting multigraph is 2-vertex-connected. Recent work gives $O^*(k^{O(k)})$-time algorithms for unweighted λ-vertex-connectivity augmentation for every λ ≤ 4 [Carmesin and Ramanujan\, SODA 2026]\, and an $O^*((k + λ)^{O(k)})$-time algorithm for arbitrary λ [Korhonen and Thorup\, FOCS 2026]. We give a deterministic algorithm with running time $O^*(36^k W)$. Thus\, for λ = 2\, the unweighted running time improves from $O^*(k^{O(k)})$ to $O^*(36^k)$\, and the algorithm also handles link costs with pseudo-polynomial dependence on $W$. \nWe reduce the problem to a boundary-pair variant of 2-vertex-connected spanning subgraph\, where each vertex is assigned a pair of incident edges with an associated pair cost. We solve this variant using a cancellation identity\, inspired by Cut&Count [Cygan et al.\, TALG 2022]\, obtained by applying Möbius inversion to decompositions along cut vertices: the identity cancels every connected spanning graph with more than one block and keeps exactly the 2-vertex-connected spanning graphs.
URL:https://dimag.ibs.re.kr/event/2026-08-04/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20260805T163000
DTEND;TZID=Asia/Seoul:20260805T173000
DTSTAMP:20260725T142224Z
CREATED:20260520T141609Z
LAST-MODIFIED:20260725T142224Z
UID:12683-1785947400-1785951000@dimag.ibs.re.kr
SUMMARY:Meike Hatzel\, Directed tree-cutwidth and immersions
DESCRIPTION:The first major step towards the graph minor structure theorem by Robertson and Seymour was the grid theorem\, a result describing that every graph of large treewidth contains a grid as minor. In 2014 Wollan gave a definition for a tree-like decomposition and a width parameter tree-cutwidth with respect to immersions\, a different graph containment relation. He provided results linking this parameter to immersions of large walls. This talk presents a version of this parameter for directed graphs\, the directed tree-cutwidth. The main result is a grid theorem for directed tree-cutwidth establishing that it is linked to directed immersions of large cylindrical walls. \nThe presented work is joined with Marcin Briański\, Karolina Okrasa\, and Michał Pilipczuk.
URL:https://dimag.ibs.re.kr/event/2026-08-05/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20260818T163000
DTEND;TZID=Asia/Seoul:20260818T173000
DTSTAMP:20260730T134943Z
CREATED:20260326T020259Z
LAST-MODIFIED:20260730T134943Z
UID:12486-1787070600-1787074200@dimag.ibs.re.kr
SUMMARY:Jinyoung Park (박진영)\, A reformulation of Talagrand's Discrete Convexity Conjecture
DESCRIPTION:The “Convexity Conjecture” by Talagrand asks\, roughly speaking\, whether one can “create convexity” in a bounded number of steps regardless of the dimension of the ambient space. Talagrand also proposed a discrete version of this conjecture\, calling it his “lifetime favorite problem” and offering a $1\,000 prize for its solution. While the continuous version of the conjecture was recently proven by Hua\, Song\, and Tudose\, the discrete analogue remains wide open. In this talk\, we introduce a reformulation of the discrete convexity conjecture using the new notion of “k-thresholds\,” an extension of the traditional definition of thresholds. Using this framework\, we establish the conjecture for several special cases\, focusing primarily on graph properties.
URL:https://dimag.ibs.re.kr/event/2026-08-18/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20260901T163000
DTEND;TZID=Asia/Seoul:20260901T173000
DTSTAMP:20260801T015407Z
CREATED:20260801T015407Z
LAST-MODIFIED:20260801T015407Z
UID:13026-1788280200-1788283800@dimag.ibs.re.kr
SUMMARY:Ben Lund\, TBA
DESCRIPTION:
URL:https://dimag.ibs.re.kr/event/2026-09-01/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20260922T163000
DTEND;TZID=Asia/Seoul:20260922T173000
DTSTAMP:20260802T034024Z
CREATED:20260717T080520Z
LAST-MODIFIED:20260802T034024Z
UID:12910-1790094600-1790098200@dimag.ibs.re.kr
SUMMARY:David Wood\, Proof of the Clustered Hadwiger Conjecture
DESCRIPTION:Hadwiger famously conjectured that every $K_h$-minor-free graph is properly $(h-1)$-colourable. This talk will present the following improper analogue of Hadwiger’s Conjecture: for fixed $h$\, every $K_h$-minor-free graph is $(h-1)$-colourable with monochromatic components of bounded size. The number of colours is best possible regardless of the size of monochromatic components. This solves an open problem of Edwards\, Kang\, Kim\, Oum and Seymour [SIAM J. Disc. Math. 2015]\, and concludes a line of research initiated in 2007. Similarly\, for fixed $t\geqslant s$\, we show that every $K_{s\,t}$-minor-free graph is $(s+1)$-colourable with monochromatic components of bounded size. The number of colours is best possible\, solving an open problem of van de Heuvel and Wood [J. London Math. Soc. 2018]. We actually prove a single theorem from which both of the above results are immediate corollaries. For an excluded apex minor\, the result is strengthened  as follows: for fixed $t \geqslant s \geqslant 3$\, and for any fixed apex graph $X$\, every $K_{s\,t}$-subgraph-free $X$-minor-free graph is $(s+1)$-colourable with monochromatic components of bounded size. The number of colours is again best possible. This is joint work with Vida Dujmović\, Louis Esperet and Pat Morin [arXiv:2306.06224].
URL:https://dimag.ibs.re.kr/event/2026-09-22/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR