J. Pascal Gollin, Dominated balanced separators in wheel-induced-minor-free graphs
2026-06-09 16:30 - 17:30 (Asia/Seoul) | Room B332, IBS (기초과학연구원)
The grid theorem of Robertson and Seymour can be equivalently stated using balanced separators, that are separators whose deletion leaves every component with no more than half of the vertices of the graph, as follows. Every graph that excludes some planar graph as a minor has a balanced separator of bounded size. Building on this formulation, Gartland and Lokshtanov conjectured an induced minor version of that theorem inspired by coarse graph theory. They conjectured that every graph that excludes some planar graph as an induced minor has a balanced separator which is dominated by a bounded number of vertices. We confirm this conjecture for excluding any fixed wheel, that is, a cycle together with a universal vertex, as an induced minor.
This talk is based on joint work with Maria Chudnovsky, Matjaž Krnc, and Martin Milanič.

Harry Richman, Distinguishing graphs with tropical Weierstrass weights
2026-06-16 16:30 - 17:30
I will introduce a new structure on finite graphs, which takes the form of a labeling of the vertices by nonnegative integers (possibly repeated). This labeling is isomorphism invariant, and seems to reflect some mix of local and global structure of the graph. I will describe an algorithm for computing these labels, which uses a form of breadth-first search, and some results on the resulting labels. This construction comes from a tropical analogue of Weierstrass weights on algebraic curves, studied in the 1800s. Finally, I will discuss some speculation on whether this may or may not be helpful for the graph isomorphism problem.
This is a joint work with Omid Amini and Lucas Gierczak.

Stefan Weltge, The relaxation complexity of the standard simplex is logarithmic
2026-06-19 16:30 - 17:30
For a set $X$ of integer points, the relaxation complexity $operatorname{rc}(X)$ is the smallest number of facets of any polyhedron P whose integer points are precisely those of X. In this paper, we focus on the case where X is the discrete standard simplex $Delta_d = {0, e_1, …, e_d}$. We show that $operatorname{rc}(Delta_d) = O(log d)$ by an explicit, elementary construction. This improves upon the previously best-known upper bound $operatorname{rc}(Delta_d) = O(d / sqrt{log d})$ due to Aprile, Averkov, Di Summa, and Hojny (2022) and matches an asymptotic lower bound by Averkov and Schymura (2020). This is joint work with Simon Keil.

Ting-Wei Chao, The Oddtown Problem Modulo a Composite Number
2026-07-10 16:30 - 17:30
A family of sets in $[n]$ is called an $ell$-Oddtown if the sizes of all sets are not divisible by $ell$, but the sizes of pairwise intersections are divisible by $ell$. The problem was completely solved when $ell$ is a prime via an elegant linear algebraic method, showing that the family has size at most $n$. However, not much was known for composite numbers. By splitting the family into families correspond to each prime factor of $ell$, one can show that the number is at most $omega n$, where $omega$ is the number of prime factors of $ell$. We used both combinatorial and Fourier analytic arguments to prove that the number of sets in any $ell$-Oddtown is at most $omega n-(2omega+varepsilon)log_2 n$ for most $n,ell$.

Yaobin Chen, Maximum in-general-position set in a random subset of $mathbb{F}^d_q$
2026-07-14 16:30 - 17:30
Let $alpha(mathbb{F}_q^{d},p)$ be the maximum possible size of a point set in general position in a $p$-random subset of $mathbb{F}_q^d$. We determine the order of magnitude of $alpha(mathbb{F}_q^{d},p)$ up to a polylogarithmic factor by proving the balanced supersaturation conjecture of Balogh and Luo. Our result also resolves a conjecture implicitly posed by the first author, Liu, the second author and Zeng. In the course of our proof, we establish a lemma that demonstrates a “structure vs. randomness” phenomenon for point sets in finite-field linear spaces, which may be of independent interest.
This is joint work with Jiaxi Nie, Jing Yu, and Wentao Zhang.

Sang-il Oum (엄상일), A proof of the cycle double cover conjecture by OpenAI
2026-07-16 16:30 - 17:30
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.
On 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.

Zichao Dong, $k$-wise odd-even towns
2026-07-21 16:30 - 17:30
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.

Stephan Kreutzer, Disjoint Paths in Graphs and Digraphs
2026-07-28 16:30 - 17:30
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$.
For 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.
In 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.

Tomohiro Koana, A Single-Exponential FPT Algorithm for 2-Vertex-Connectivity Augmentation
2026-08-04 16:30 - 17:30
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$.
We 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.

Meike Hatzel, Directed tree-cutwidth and immersions
2026-08-05 16:30 - 17:30
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.
The presented work is joined with Marcin Briański, Karolina Okrasa, and Michał Pilipczuk.

Hyunwoo Lee (이현우), A super-exponential lower bound construction for the multicolor triangle Ramsey problem discovered by OpenAI
2026-08-07 15:00 - 16:00
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 ErdH{o}s whether $R_k(3)$ grows exponentially or super-exponentially in $k$.
On 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.

Jinyoung Park (박진영), A reformulation of Talagrand's Discrete Convexity Conjecture
2026-08-18 16:30 - 17:30
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.

Ben Lund, Incidences between points and n-flats in PG(n+d,q)
2026-09-01 16:30 - 17:30
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$.

Olga Medrano Martín del Campo, Epsilon-saturation for Littlestone classes and stable graphs
2026-09-08 16:30 - 17:30
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.

Gabriëlle Zwaneveld, On Seymour-tight orientations
2026-09-15 16:30 - 17:30
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.
Using 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.
The 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.

David Wood, Proof of the Clustered Hadwiger Conjecture
2026-09-22 16:30 - 17:30
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 $tgeqslant 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].

Daniel McGinnis, Multi-generic initial ideals, regularity, and the optimal colorful fractional Helly theorem for $d$-Leray complexes
2026-10-06 16:30 - 17:30
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.
We 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.
As an application, we prove the optimal fractional Helly theorem for $d$-Leray simplicial complexes, a problem stemming from the work of Kim in 2017.

Julien Codsi, Recent progress in the tree-⍺ world
2026-10-13 16:30 - 17:30
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.
