BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.17.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: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:20260807T150000
DTEND;TZID=Asia/Seoul:20260807T160000
DTSTAMP:20260804T132550Z
CREATED:20260804T132550Z
LAST-MODIFIED:20260804T132550Z
UID:13051-1786114800-1786118400@dimag.ibs.re.kr
SUMMARY:Hyunwoo Lee (이현우)\, A super-exponential lower bound construction for the multicolor triangle Ramsey problem discovered by OpenAI
DESCRIPTION:Let $R_k(3)$ denote the smallest integer $N$ such that every $k$-edge-coloring of the complete graph $K_N$ contains a monochromatic triangle. A simple inductive argument gives the classical factorial upper bound $R_k(3)\leq k!=k^{O(k)}$\, whereas the best previously known lower bound was only exponential in $k$\, namely\, $R_k(3)\geq 2^{\Omega(k)}$. It was a longstanding open problem of Erd\H{o}s whether $R_k(3)$ grows exponentially or super-exponentially in $k$. \nOn August 1\, 2026\, OpenAI\, using an internal AI model\, discovered a construction establishing the super-exponential lower bound $R_k(3)\geq k^{\Omega(k)}$\, thereby resolving Erdős’ longstanding question. In this talk\, I will explain the construction and discuss possible directions for further research\, some of which may already have been explored by other researchers.
URL:https://dimag.ibs.re.kr/event/2026-08-07/
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:20260825T042634Z
CREATED:20260801T015407Z
LAST-MODIFIED:20260825T042634Z
UID:13026-1788280200-1788283800@dimag.ibs.re.kr
SUMMARY:Ben Lund\, Incidences between points and n-flats in PG(n+d\,q)
DESCRIPTION:Let $P$ be a set of points in $PG(n+d\,q)$\, and let $L$ be a set of $n$-flats. Here\, $n$-flat is a short name for $n$-dimensional projective subspaces. A classical bound of Haemers\, rediscovered in an influential paper of Vinh\, gives an upper bound on the difference between the number of incidences between $P$ and $L$ and the expected number of incidences for random sets of points and flats with the same cardinalities as $P$ and $L$. Haemers’ bound is tight as a function of $|P|$ times $|L|$. Recent work of Kong and Tamo improves the bound under the assumption that $|L|$ is not too large. I will discuss recent work\, joint with Tao Zhang\, that improves the bound of Kong and Tamo. The proof depends on an independently interesting upper bound on the number of pairs $(l_1\,l_2)$ of flats in $L$ such that $\dim(l_1 \cap l_2)=j$\, for $0 \leq j \leq n$.
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:20260908T163000
DTEND;TZID=Asia/Seoul:20260908T173000
DTSTAMP:20260825T051917Z
CREATED:20260812T064149Z
LAST-MODIFIED:20260825T051917Z
UID:13089-1788885000-1788888600@dimag.ibs.re.kr
SUMMARY:Olga Medrano Martín del Campo\, Epsilon-saturation for Littlestone classes and stable graphs
DESCRIPTION:We introduce the concept of the saturation of a (bi)graph: the union closure after inductively adding its virtual elements\, which are weighted ε-good (respectively ε-excellent sets) as in the Stable Regularity Lemma. In the Littlestone class and stable graph case\, we show that if the saturation has bounded Littlestone dimension\, then it is the smallest ε-saturated object containing the initial one. We show that for certain values of ε\, the saturations of Littlestone classes are Littlestone\, although not necessarily of the same dimension. For ε large enough\, we find examples to show that VC and Littlestone dimensions may grow arbitrarily. For certain ε\, we bound Littlestone dimension of the saturation by a finite value depending on VC dimension\, by using techniques including the Fundamental Theorem of Statistical Learning and the Littlestone Minimax Theorem. We will focus on the class (or bigraph) case and time permitting\, we will discuss the stable graph case. Joint work with Maryanthe Malliaris and Shay Moran.
URL:https://dimag.ibs.re.kr/event/2026-09-08/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20260915T163000
DTEND;TZID=Asia/Seoul:20260915T173000
DTSTAMP:20260821T131519Z
CREATED:20260821T131407Z
LAST-MODIFIED:20260821T131519Z
UID:13138-1789489800-1789493400@dimag.ibs.re.kr
SUMMARY:Gabriëlle Zwaneveld\, On Seymour-tight orientations
DESCRIPTION:I discuss ‘almost counterexamples’ to Seymour’s second neighbourhood conjecture. In what we call Seymour-tight orientations\, the size of the first neighbourhood of each vertex equals the size of its second neighbourhood. We give several examples and constructions. Specifically\, we prove that the class of Seymour-tight orientations is closed under taking (generalized) lexicographic products. Moreover\, the lexicographic product of a putative counterexample to Seymour’s second neighbourhood conjecture and a Seymour-tight orientation is again a counterexample. \nUsing lexicographic products\, we show that if the conjecture is false\, then there exist counterexamples that are close to regular tournaments\, and moreover that any digraph occurs as an induced subgraph of a counterexample. We then use this same machinery to construct special putative counterexamples to Sullivan’s conjecture. \nThe inherent symmetry of these orientations give access to an algebraic perspective. Seymour-tight orientations that are also Cayley digraphs correspond to special pairs of critical sets in groups\, which connects potentially to additive combinatorics. We use Kemperman’s theorem to characterize those Seymour-tight orientations that are the Cayley digraph of an abelian group.
URL:https://dimag.ibs.re.kr/event/2026-09-15/
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
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20261006T163000
DTEND;TZID=Asia/Seoul:20261006T173000
DTSTAMP:20260821T005558Z
CREATED:20260821T005539Z
LAST-MODIFIED:20260821T005558Z
UID:13133-1791304200-1791307800@dimag.ibs.re.kr
SUMMARY:Daniel McGinnis\, Multi-generic initial ideals\, regularity\, and the optimal colorful fractional Helly theorem for $d$-Leray complexes
DESCRIPTION:A celebrated result of Bayer and Stillman from 1987 states that for a homogeneous ideal $I$ of a polynomial ring $S$\, the regularities of $S/I$ and $S/\textrm{GIN}(I)$ are the same under the reverse lexicographic monomial ordering\, where $\textrm{GIN}(I)$ is the generic initial ideal. If $R$ is a polynomial ring whose variables are subdivided into disjoint blocks of variables $X_1\,\dots\,X_c$\, there is a natural multi-grading on $R$\, and one can analogously define a multi-graded version of the generic initial ideal for any multi-homogeneous ideal $I$ of $R$. However\, the full strength of the Bayer-Stillman Theorem fails in the multi-graded setting; there are multi-homogeneous ideals $I$ such that the regularities are not preserved after passing to the multi-graded generic initial ideal no matter the choice of monomial ordering. \nWe prove lower bounds on the regularity of $R/I$ in terms of almost regular sequences of the multi-graded generic initial ideal of $I$ restricted to each block of variables. Again\, we use the reverse lexicographic monomial ordering\, but interestingly\, the lower bound result requires a particular choice of ordering on the variables. \nAs an application\, we prove the optimal fractional Helly theorem for $d$-Leray simplicial complexes\, a problem stemming from the work of Kim in 2017.
URL:https://dimag.ibs.re.kr/event/2026-10-06/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20261013T163000
DTEND;TZID=Asia/Seoul:20261013T173000
DTSTAMP:20260819T090026Z
CREATED:20260811T214705Z
LAST-MODIFIED:20260819T090026Z
UID:13078-1791909000-1791912600@dimag.ibs.re.kr
SUMMARY:Julien Codsi\, Recent progress in the tree-⍺ world
DESCRIPTION:Treewidth is a graph parameter commonly used to quantify how “close” a graph is to a tree. Although it is a cornerstone of structural graph theory and algorithm design\, it is nearly useless for algorithmic purposes in many dense graph classes. In this talk\, we discuss the tree-independence number\, a more versatile graph parameter that replaces the standard width measure with the stability number. We will present recent results aimed at characterizing the graph classes in which this parameter enables sub-exponential time algorithms for problems that are\, in general\, NP-hard.
URL:https://dimag.ibs.re.kr/event/2026-10-13/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR