Discrete Mathematics Group

Hidde Koerts, Characterizing large clique number in tournaments
2026-03-24 16:30 - 17:30 (Asia/Seoul) | Room B332, IBS (기초과학연구원)
A backedge graph of a tournament $T$ with respect to a total ordering $prec$ of the vertices of $T$ is a graph on $V(T)$ where $uv$ is an edge if and only if $uv in A(T)$ and $v prec u$. In 2023, Aboulker, Aubian, Charbit and Lopes introduced the clique number of tournaments based on backedge graphs as a natural counterpart to the dichromatic number of tournaments. Specifically, the clique number of a tournament is the minimum clique number of a backedge graph when considering all possible orderings.
Given this definition, it is not immediately clear what the canonical clique object should be. In this talk, we provide an answer to this question. We show that if a tournament has large clique number, it contains a reasonably large subtournament from one of two simple and previously studied families of tournaments of unbounded clique number.
This talk is based on joint work with Logan Crew, Xinyue Fan, Benjamin Moore, and Sophie Spirkl.

Tung H. Nguyen, Polynomial χ-boundedness for excluding the five-vertex path
2026-03-31 16:30 - 17:30 | Room B332, IBS (기초과학연구원)
We overview the recent resolution of a 1985 open problem of Gyárfás, that chromatic number is polynomially bounded by clique number for graphs with no induced five-vertex path. The proof introduces a chromatic density framework involving chromatic quasirandomness and chromatic density increment, which allows us to deduce the desired statement from the Erdős–Hajnal result for the five-vertex path.

Mamadou Moustapha Kanté, Strongly flip-flat classes of graphs
2026-04-07 16:30 - 17:30 | Room B332, IBS (기초과학연구원)
Strong flip-flatness appears to be the analogue of uniform almost-wideness in the setting of dense classes of graphs. Almost-wideness is a notion that was central in different characterisations of nowhere dense classes of graphs, and in particular the game-theoretic one. In this talk I will present the flip-flatness notions and conjectures about the characterization of strongly flip-flat graph classes. Then, I will present a proof that strongly flip-flat classes of graphs that are weakly sparse are indeed uniformly almost-wide, making a step towards their characterisation. A consequence is a characterization of strongly flip-flat graph classes with low rank-depth colourings.
This is a joint work with F. Ghasemi, J. Grange and F. Madelaine.

Xin Wei, Separating hash families with large universe
2026-04-28 16:30 - 17:30 | Room B332, IBS (기초과학연구원)
Separating hash families are useful combinatorial structures that generalize several well-studied objects in cryptography and coding theory. Let $p_t(N, q)$ denote the maximum size of the universe for a $t$-perfect hash family of length $N$ over an alphabet of size $q$. We show that $q^{2 – o(1)} < p_t(t, q) = o(q^2)$ for all $t ge 3$, thereby resolving an open problem raised by Blackburn et al. (2008) for certain parameter ranges. Previously, this result was known only for $t = 3$ and $t = 4$. Our approach establishes the existence of a large set of integers that avoids nontrivial solutions to a system of correlated linear equations. This is joint work with Xiande Zhang and Gennian Ge.

Maximilian Gorsky, The Disjoint Paths Problem lies in the Oort cloud of algorithms
2026-05-06 16:30 - 17:30 | Room B332, IBS (기초과학연구원)
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.
Joint work with Dario Cavallaro, Stephan Kreutzer, Dimitrios Thilikos, and Sebastian Wiederrecht.

Benjamin Duhamel, Excluding a forest induced minor
2026-05-12 16:30 - 17:30 | Room B332, IBS (기초과학연구원)
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.
This is a joint work with É. Bonnet and R. Hickingbotham.

Xavier Goaoc, A canonical tree decomposition for order types, and some applications
2026-05-19 16:30 - 17:30 | Room B332, IBS (기초과학연구원)
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.
This is joint work with Mathilde Bouvel, Valentin Féray, and Florent Koechlin.

Fernanda Rivera Omaña, Erdős-Pósa theorem for matroids
2026-05-26 16:30 - 17:30 | Room B332, IBS (기초과학연구원)
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.
This is joint work with James Davies and Meike Hatzel.

Maria Chudnovsky, Induced minors and treewidth
2026-06-02 16:30 - 17:30 | Room B332, IBS (기초과학연구원)
This talk deals with induced minor obstructions to treewidth. The natural setup for this problem is to consider the class of graphs excluding some planar graph, and some complete bipartite graph as induced minors, and some complete graph as a subgraph. Unfortunately, such classes still contain graphs of arbitrarily large treewidth. Moreover, a result of Alecu, Bonnet, Bureo Villafana and Trotignon and its extensions suggest that there is no elegant characterization of families of bounded treewidth in terms of induced obstructions.
On the other hand, it is conjectured that graphs in the classes as above have treewidth bounded by a poly-logarithmic function of their number of vertices. If true, this will imply the existence of quasi-polynomial time algorithms for a host of problems on such classes that are NP-complete in the general setting.
While this conjecture remains open, in joint work with Julien Codsi, David Fischer and Daniel Lokshtanov, we were able to prove the existence of a sub-polynomial bound on treewidth in terms of the number of vertices. This in turn leads to sub-exponential algorithmic behavior.
In this talk we will discuss some ideas of the proof, and, if time permits, some results in the more general setting when the bound on the clique size is removed.

J. Pascal Gollin, Dominated balanced separators in wheel-induced-minor-free graphs
2026-06-09 16:30 - 17:30 | 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 | Room B332, IBS (기초과학연구원)
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 | Room B332, IBS (기초과학연구원)
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.

2026 Workshop on Topological Combinatorics
2026-06-28 - 2026-07-11 | GIST
The 2026 Workshop on Topological Combinatorics will be held from June 28 to July 11, 2026 at Gwangju Institute of Science and Technology (GIST), located in Gwangju in the southwest of Republic of Korea.
The workshop aims to bring together researchers interested in applications of topology to combinatorics and related areas. This will be the fifth workshop in a series initiated by Ron Aharoni (August 2018 in Shantou, July 2019 in Prague, July 2020 on Zoom, and June 2024 in Paris).
The first week (June 28 – July 04) will be reserved for presentations, while the following days (July 05 – July 11) will be for discussion and collaborations.
The campus offers a variety of amenities, including a guesthouse that can accommodate approximately 20 guests.
In addition, various lodging options are available within a 15–20 minute walking distance.
We are planning to provide accommodation for all invited participants, and we are also considering offering partial travel support for those with limited funding.

Website: https://sites.google.com/view/2026topocomb

Ting-Wei Chao, The Oddtown Problem Modulo a Composite Number
2026-07-10 16:30 - 17:30 | Room B332, IBS (기초과학연구원)
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 | Room B332, IBS (기초과학연구원)
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.

Zichao Dong, TBA
2026-07-21 16:30 - 17:30 | Room B332, IBS (기초과학연구원)

2026 Korean Student Combinatorics Workshop
2026-07-27 - 2026-07-31 | Gongju Hanok Village, Gongju
Website: https://kscw.combinatorics.kr/

Stephan Kreutzer, TBA
2026-07-28 16:30 - 17:30 | Room B332, IBS (기초과학연구원)

Tomohiro Koana, TBA
2026-08-04 16:30 - 17:30 | Room B332, IBS (기초과학연구원)

Meike Hatzel, TBA
2026-08-05 16:30 - 17:30 | Room B332, IBS (기초과학연구원)

2026 Summer School on Combinatorics and Algorithms (2026 조합론 및 알고리즘 여름학교)
2026-08-10 - 2026-08-14 | Bldg. E11, KAIST
The 2026 Summer School on Combinatorics and Algorithms is a venue for students and early-career researchers to learn selected topics in theoretical computer science and discrete mathematics. It will be a great opportunity for young and aspiring researchers to study topics which are important but not covered during the lectures in the university classes.
Website: https://combialgo.dimag.kr/2026/
Lecturers and Topics

Daniel Dadush, CWI, Amsterdam

Algorithms & Geometry of Linear Programming

Magnus Wahlström, Royal Holloway, University of London

Matroids, delta-matroids, and applications

Schedule

Start on 10 August 2026 Monday, 2 PM
End on 14 August 2025 Friday, 5 PM

Jinyoung Park (박진영), TBA
2026-08-18 16:30 - 17:30 | Room B332, IBS (기초과학연구원)

2026 Combinatorics Workshop (2026 조합론 학술대회)
2026-10-20 - 2026-10-22 | Konjiam Resort, EW Village, B2, Meeting Room OPUS2
Combinatorics Workshop (조합론 학술대회) is an annual conference for researchers in combinatorics and related areas in Korea. It was started in 2004 by the Yonsei University BK21 Research Group. Since 2013, this workshop has been advised by the committee of discrete mathematics of the Korean Mathematical Society.
Website: https://cw2026.combinatorics.kr/en/
Venue
Konjiam Resort, EW Village, B2, Meeting Room OPUS2
(278, Docheogwit-Ro, Docheok-Myeon, Gwangju-Si, Gyeonggi-Do, Korea)

Travel Instructions

Dates
October 20 to 22, 2026
Plenary Speaker
Alexander V. Kostochka (UIUC)
Invited Speakers

Cheolwon Heo (SUNY Korea)
Tony Huynh (IBS DIMAG)
Dabeen Lee (Seoul National University)
Jongbaek Song (Pusan National University)

Contributed Talks
Each contributed talk will be about 20 minutes, including questions. Please note that we may stop accepting contributed talk applications before the deadline if all available slots are filled.
If you are interested in giving a contributed talk at the workshop, please submit an abstract by August 31, 2026.
To apply for a contributed talk, go to Call for Abstracts on Indico and click “Submit new abstract.” You may need to create an IBS Indico account.
Registration
Registration link
The registration deadline is August 31, 2026.
Organizing Committee

Ilkyoo Choi (최일규), Hankuk University of Foreign Studies, IBS Discrete Mathematics Group, KIAS
Sang-il Oum (엄상일), IBS Discrete Mathematics Group
Boram Park (박보람), Seoul National University

Advisory Committee
Committee of Discrete Mathematics, The Korean Mathematical Society (Chair: Sang-il Oum)
Sponsors

IBS Discrete Mathematics Group
Korean Mathematical Society
Seoul National University
Hankuk University of Foreign Studies
