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:20260716T163000
DTEND;TZID=Asia/Seoul:20260716T173000
DTSTAMP:20260714T132114Z
CREATED:20260714T132005Z
LAST-MODIFIED:20260714T132114Z
UID:12891-1784219400-1784223000@dimag.ibs.re.kr
SUMMARY:Sang-il Oum (엄상일)\, A proof of the cycle double cover conjecture by OpenAI
DESCRIPTION:The cycle double cover conjecture (CDC) claims that every graph without cut-edges has a list of cycles such that every edge appears exactly twice in the list. This conjecture was proposed in 1970s by several mathematicians independently\, including Tutte\, Seymour\, and Szekeres. \nOn July 10\, 2026\, OpenAI released a proof found by its ChatGPT 5.6 Sol Ultra. I will explain a slightly modified proof\, with the aim of making it mostly accessible to undergraduate students.
URL:https://dimag.ibs.re.kr/event/2026-07-16/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20260721T163000
DTEND;TZID=Asia/Seoul:20260721T173000
DTSTAMP:20260713T060115Z
CREATED:20260711T143148Z
LAST-MODIFIED:20260713T060115Z
UID:12865-1784651400-1784655000@dimag.ibs.re.kr
SUMMARY:Zichao Dong\, $k$-wise odd-even towns
DESCRIPTION:For $\boldsymbol{\alpha} = (\alpha_1\, \dots\, \alpha_k) \in {\mathbb F}_2^k$\, an $\boldsymbol{\alpha} $-town is a set family in which every $i$-wise intersection has parity $\alpha_i$. Denote by $f_{\boldsymbol{\alpha} }(n)$ the maximum size of an $\boldsymbol{\alpha} $-town on $[n]$. The classical oddtown and eventown problems study the cases $\boldsymbol{\alpha} = (1\, 0)$ and $(0\, 0)$\, respectively. We determine the sharp asymptotics of $f_{\boldsymbol{\alpha} }(n)$ for all $\boldsymbol{\alpha} $\, answering questions of Johnston-O’Neill and Wei-Zhang-Ge.
URL:https://dimag.ibs.re.kr/event/2026-07-21/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20260728T163000
DTEND;TZID=Asia/Seoul:20260728T173000
DTSTAMP:20260717T125139Z
CREATED:20260616T000638Z
LAST-MODIFIED:20260717T125139Z
UID:12768-1785256200-1785259800@dimag.ibs.re.kr
SUMMARY:Stephan Kreutzer\, Disjoint Paths in Graphs and Digraphs
DESCRIPTION:One of the important algorithmic consequences of Robertson and Seymour’s Graph Minor Project is their proof that the k-Vertex-Disjoint Paths problem is fixed-parameter tractable on the class of all undirected graphs\, that is\, solvable in time $f(k) \cdot n^c$\, for some function $f$ and constant $c$. \nFor directed graphs the problem is significantly harder: the k-Disjoint-Paths problem it is NP-complete already for $k=2$. While this indicates that the Directed-k-Disjoint Paths problem is unlikely to be fixed-parameter tractable in general\, it is nevertheless interesting to investigate which of the techniques used to solve the problem on undirected graphs fail for digraphs and why and whether some of them can be made to work in a more restricted setting. \nIn this talk I will speak about recent results on disjoint directed paths including positive solutions for special graph classes such as Eulerian digraphs but also recently obtained further hardness results.
URL:https://dimag.ibs.re.kr/event/2026-07-28/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
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:20260326T020259Z
CREATED:20260326T020259Z
LAST-MODIFIED:20260326T020259Z
UID:12486-1787070600-1787074200@dimag.ibs.re.kr
SUMMARY:Jinyoung Park (박진영)\, TBA
DESCRIPTION:
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:20260922T163000
DTEND;TZID=Asia/Seoul:20260922T173000
DTSTAMP:20260717T080520Z
CREATED:20260717T080520Z
LAST-MODIFIED:20260717T080520Z
UID:12910-1790094600-1790098200@dimag.ibs.re.kr
SUMMARY:David Wood\, TBA
DESCRIPTION:
URL:https://dimag.ibs.re.kr/event/2026-09-22/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR