We give a new proof of the fact that every 2-coloring of the positive integers contains a monochromatic Pythagorean triple. This result was originally proven by Heule, Kullmann, and Marek with SAT sol...

We show that the associahedron $\mathcal{A}_n$ has chromatic number $O(\log\log n)$, improving on the previously best known upper bound of $O(\log n)$.

For a class of Fibonacci-like unimodal maps, the restriction to the $ω$-limit set of the unique turning point defines a minimal Cantor system. We construct these Cantor sets geometrically using a nest...

A $D$-diffsequence is a sequence of integers $x_1 < \dots < x_k$ such that $x_{i+1} -x_i \in D$ for $1 \le i \le k-1$. The set $D$ is called $r$-accessible if every $r$-coloring of the positive intege...

For an $n$-element matroid $M$ given by an $n \times n$ matrix representation over a finite field $\mathbb F$ and an integer $k$, we present an algorithm with running time $O_{k,\mathbb F}(n^2)+O(n^ω)...

On September 22, 2026, David R. Wood from Monash University gave a talk on coloring graphs without K_t minor with t colors while avoiding large monochromatic components at the Discrete Math Seminar. The title of his talk was "Proof of the Clustered Hadwiger Conjecture".

On September 18, 2026, David R. Wood from Monash University gave a talk showing the proof of the Erdős-Sós conjecture found by GPT Astra at the Discrete Math Seminar. The title of his talk was "The Erdős-Sós Theorem".

On September 15, 2026, Gabriëlle Zwaneveld from University of Amsterdam gave a talk on oriented graphs with the same number of neighbors and second neighbors at each vertex movited by … Continue readi...

The IBS Discrete Mathematics Group (DIMAG) in Daejeon, Korea invites applications for four research fellowship positions (senior researcher positions). DIMAG is a research group that was established on December 1, 2018 at the Institute for Basic Science (IBS), led by its Chief Investigator (CI) Sang-il Oum. DIMAG is located at the headquarters of IBS in Daejeon, South Korea, a city of 1.5 million people.

The IBS Discrete Mathematics Group held the "2026 DIMAG Internal Workshop" at the Kensington Resort in Namwon on September 9-13, 2026. Participants included all but one of DIMAG's current members, as well as Sebastian Wiederrecht (KAIST), Minki Kim (GIST), Seonghyuk Im (KIAS), and Hojin Chu (KIAS). Every participant presented open problems, and there were active discussions throughout, leading to several progress reports.

Read the declaration and add your name.

Let $P_t$ denote the induced path on $t$ vertices. Let $ω(G)$ denote the maximum number of vertices in a clique of a graph $G$. Gyárfás (1987) proved that every $P_t$-free graph $G$ satisfies $χ(G)\le...

On September 1, 2026, Ben Lund from Xidian University, China gave a talk at the Discrete Math Seminar on an upper bound of the number of incidences between points and n-dimensional projective subspaces in PG(n+d,q). The title of his talk was "Incidences between points and n-flats in PG(n+d,q)".

We present a Rice-like complexity lower bound for any MSO-definable problem on binary structures succinctly encoded by circuits. This work extends the framework recently developed as a counterpoint to...

On September 8, 2026, Olga Medrano Martín del Campo from the IBS Discrete Mathematics Group gave a talk on -saturation of classes of graphs of bounded Littlestone dimension and VC dimension at the Discrete Math Seminar. The title of her talk was "Epsilon-saturation for Littlestone classes and stable graphs".

In this paper we introduce a generalization of Helly's theorem closely connected to Bárány-Gromov overlap theorems (also called selection lemmas). Our main result implies both the topological colorful...

Let $P_t$ denote the induced path on $t$ vertices. Let $ω(G)$ denote the maximum number of vertices in a clique of a graph $G$. Previously Gyárfás (1987) proved that every $P_t$-free graph $G$ satisfi...

Cycle rank is a depth parameter for digraphs introduced by Eggan in 1963. Gruber (DMTCS 2012) and Giannopoulou, Hunter, and Thilikos (DAM 2012) asked whether the problem of determining if a given digr...

Debsoumya Chakraborti (দেবসৌম্য চক্রবর্তী) Assistant ProfessorIIT Bombay I am an assistant professor in the Department of Mathematics at IIT Bombay, India. My research interest broadly lies in Combi...

Donggyu Kim is a postdoctoral fellow at Georgia Tech working on matroid theory and algebraic combinatorics.

The IBS Discrete Mathematics Group welcomes Dr. Xiying Du, a new research fellow at the IBS Discrete Mathematics Group, starting on September 1, 2026. She received her Ph.D. from the Georgia Institute of Technology under the supervision of Prof. Rose McCarty and Prof. Xingxing Yu. She is interested in structural graph theory, in particular graph linkages, degree-boundedness, and induced subgraphs.

The IBS Discrete Mathematics Group welcomes Dr. William J. Wesley, a new research fellow at the IBS Discrete Mathematics Group, starting September 1, 2026. He received his Ph.D. from the University of California, Davis under the supervision of Prof. Jesús A. De Loera. Until recently, he was an SEW Visiting Assistant Professor at the University of California, San Diego. His research is focused primarily on computational Ramsey theory, and he is more broadly interested in combinatorics, algebra, and optimization.

The IBS Discrete Mathematics Group welcomes Dr. Mingyuan Rong, a new research fellow at the IBS Extremal Combinatorics and Probability Group, starting September 1, 2026. Mingyuan Rong received his Ph.D. from the University of Science and Technology of China under the supervision of Prof. Jie Ma. Until recently, he was a Visiting Student Researcher at the University of Warwick, working with Prof. Oleg Pikhurko. He is interested in extremal set theory and extremal graph theory.

We study path-width and the closely related parameter line-width in countably infinite graphs. Our first result characterises the graphs of finite path-width: they are the graphs that do not have infi...

We formulate a geometric version of the Erdős-Hajnal conjecture that applies to finite projective geometries rather than graphs, in both its usual 'induced' form and the multicoloured form. The multic...

ASIACOMB 2026, the inaugural conference of the ASIACOMB series, was held at the Daejeon Convention Center (DCC) in Daejeon, Korea from August 24 to August 28, 2026. ASIACOMB is a biennial conference held in Asia that promotes international collaboration by strengthening research connections and providing a high-level forum for ideas in combinatorics. It was organized by the IBS Extremal Combinatorics and Probability Group, with Hong Liu (IBS ECOPRO) as the chair of the organizing committee, together with Felix Christian Clemen (University of Victoria), Zichao Dong (IBS ECOPRO), Seonghyuk Im (KIAS), Suyun Jiang (Jianghan University), and Zhuo Wu (Universitat Politècnica de Catalunya).

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 l...

For a graph H, an H-colouring of a graph G is a vertex mapping ϕ : V ( G ) → V ( H ) such that adjacent vertices are mapped to adjacent vertices. A graph G is C 2 k + 1-critical if G has no C...

A graph $G$ is \emph{$H$-induced-saturated} if $G$ has no induced subgraph isomorphic to $H$ but changing the adjacency of an arbitrary pair of vertices in $G$ creates an induced copy of $H$. The exis...

The Erdős-Pósa theorem states that for every integer $k\geq1$, every graph contains either $k$ vertex-disjoint cycles or a set of $\mathcal{O}(k\log k)$ vertices meeting all cycles. This fundamental m...

For a $C_4$-free graph $G$ on $n$ vertices --- one with no induced cycle on four vertices --- we study the two-sided extremal problem for the triangle density $τ$: How large and how small can $τ$ be f...

On August 18, 2026, Jinyoung Park (박진영) from NYU gave a talk at the Discrete Math Seminar on a reformulation of the Discrete Convexity Conjecture of Talagrand. The title of her talk was "A reformulation of Talagrand’s Discrete Convexity Conjecture".

The IBS discrete mathematics group welcomes Dr. Daniel McGinnis, a new research fellow at the IBS Discrete Mathematics Group from August 16, 2026. He received his Ph.D. from the University of Iowa under the supervision of Prof. Shira Zerbib in 2024 and was subsequently a postdoctoral researcher at Princeton University. He is interested in combinatorics, discrete geometry, and combinatorial topology.

About 100 people attended the 2026 Summer School on Combinatorics and Algorithms from August 10 to August 14, 2026, held at KAIST. Daniel Dadush from CWI and Magnus Wahlström from the Royal Holloway, University of London gave lectures. This school was organized by Jungho Ahn (Inha University), Eun Jung Kim (KAIST / IBS / CNRS), Eunjin Oh (POSTECH), and Sang-il Oum (IBS Discrete Mathematics Group).

For a constant $η\geq 0$, Pathwidth-$η$ Deletion is the problem of deciding whether, for a given graph $G$ and integer $k$, there is a set $S \subseteq V(G)$ of size at most $k$ such that the pathwidt...

A connectivity function on a finite set $E$ is a function $f\colon 2^E\to\mathbb Z$ that is submodular and symmetric, with $f(\varnothing)=0$. Given a connectivity function $f$ via a value oracle, ter...

Erdős, Sárközy, and Sós studied the asymptotics of the maximum size of a subset of $\{1,2,\ldots, N\}$ such that it does not contain $k$ distinct elements whose product is a perfect square. More gener...

In a recent breakthrough, Kalmynin resolved conjectures of Lev--Sonn and Sárközy on additive decompositions of multiplicative subgroups of prime fields. In this paper, inspired by a related conjecture...

On August 7, 2026, Hyunwoo Lee (이현우) from KAIST and IBS Extremal Combinatorics and Probability Group gave a talk at the Discrete Math Seminar on a recent super-exponential lower bound for the multicolor triangle Ramsey number by OpenAI. The title of his talk was "A super-exponential lower bound construction for the multicolor triangle Ramsey problem discovered by OpenAI".

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 ...

On August 5, 2026, Meike Hatzel from TU Darmstadt gave a talk at the Discrete Math Seminar on a structural characterization of digraphs not immersing a cylindrical grid. The title of her talk was "Directed tree-cutwidth and immersions".

On August 4, 2026, Tomohiro Koana from University of Tokyo gave a talk at the Discrete Math Seminar on a single-exponential fixed-parameter algorithm for enlarging a subgraph with at most k edges to make a 2-connected subgraph of a given graph. The title of his talk was "A Single-Exponential FPT Algorithm for 2-Vertex-Connectivity Augmentation".

Lokshtanov, Ramanujan, Saurabh, and Zehavi [ICALP 2018] proved that for any CMSO formula $ϕ$, testing $ϕ$ on arbitrary graphs can be reduced to testing it on $(q,k)$-unbreakable graphs for appropriate...

Sárközy conjectured that the nonzero quadratic residues modulo a sufficiently large prime have no nontrivial additive decomposition. Hanson and Petridis proved the conjecture for almost all primes, an...