Combinatorics Seminar 2025-26

For 2025-26, the Combinatorics Seminar will be held 2-3pm on Fridays in B3.02, unless otherwise stated.

In Term 3, the seminar is organised by Levente Bodnar, Jun Gao and Oleg Pikhurko. Abstracts will be added below the table when details are available.

Term 3

1st May: Cicely Henderson, University of Waterloo

On the Hypergraph Nash-Williams’ Conjecture

The study of combinatorial designs includes some of the oldest questions at the heart of combinatorics. In a breakthrough result of 2014, Keevash proved the longstanding Existence Conjecture by showing the existence of (n,q,r)-Steiner systems (equivalently K_q^r-decompositions of K_n^r) for all large enough n satisfying the necessary divisibility conditions. Meanwhile, in recent decades, incremental progress has been made on the celebrated Nash-Williams' Conjecture of 1970, which posits that any large enough, triangle-divisible graph on n vertices with minimum degree at least 3n/4 admits a triangle decomposition. In 2021, Glock, Kühn, and Osthus proposed a generalization of these results by conjecturing a hypergraph version of the Nash-Williams' Conjecture, where their proposed minimum degree K_q^r-decomposition threshold is motivated by hypergraph Turán theory. By using the recently developed method of refined absorption and establishing a non-uniform Turán theory, we tie the K_q^r-decomposition threshold to its fractional relaxation. Combined with the best-known fractional decomposition threshold from Delcourt, Lesgourgues, and Postle, this dramatically closes the gap between what was known and the above conjecture. This talk is based on joint work with Luke Postle.

6th May: Yan Wang, Shanghai Jiao Tong University

Nearly tight bound for rainbow clique subdivisions in properly edge-colored graphs and applications

An edge-colored graph is said to be rainbow if all its edges have distinct colors. In this paper, we study the rainbow analogue of a fundamental result of Mader [Math. Ann 174 (1967), 265--268] on the existence of subdivisions in graphs with large average degree. This is part of the study of rainbow analogues of classical Tur\'an problems, a framework systematically introduced by Keevash, Mubayi, Sudakov and Verstraëte [Combin. Probab. Comput. 16 (2007), 109--126]. We prove that every properly edge-colored graph on $n$ vertices with average degree at least $t^2(\log n)^{1+o(1)}$ contains a rainbow subdivision of $K_t$. When $t$ is a constant, this bound is tight up to the $o(1)$ term. So it essentially resolves a question raised by Jiang, Methuku and Yepremyan [European J. Combin. 110 (2023), 103675] on rainbow clique subdivisions, and also implies a result of Alon, Bucić, Sauermann, Zakharov and Zamir [Proc. Lond. Math. Soc. 130 (2025), e70044] on rainbow cycles. In addition, we present several applications of our result to problems in additive combinatorics, number theory and coding theory. This is joint work with Peiru Kuang.

8th May: Shumin Sun, University of warwick

Rational codegree Turán density of hypergraphs

In this talk, we investigate the codegree Turán density of families of k-uniform hypergraphs. We present two main results. First, we prove a realizability result: for every integer k at least 3, every rational number in [0, 1) is the codegree Turán density of some finite family of k-graphs. Second, we establish a strong version of non-principality. We construct two hypergraphs F_1 and F_2 such that the codegree Turán density of the pair {F_1, F_2} is strictly smaller than the density of either F_1 or F_2 individually. This answers a question posed by Mubayi and Zhao (2007).

This is joint work with Jun Gao, Oleg Pikhurko, and Mingyuan Rong.

15th May: Jie Ma, University of Science and Technology of China/Tsinghua University

An exponential improvement for Ramsey lower bounds (and beyond)

We prove a new lower bound on the Ramsey number r(\ell, C\ell) for any constant C> 1 and sufficiently large \ell, showing that there exists \varepsilon(C) > 0 such that r(\ell, C\ell) ≥ \left(p_C^{-1/2} + \varepsilon(C)\right)^\ell, where p_C denotes the unique solution in (0, 1/2) satisfying C = \log p_C / \log (1 - p_C). This provides the first exponential improvement over the classical lower bound by Erdos since 1947. We will also aim to discuss some recent development related to this approach. Joint work with Wujie Shen and Shengjie Xie.

12th June: Peiru Kuang, Shanghai Jiao Tong University

Tight bounds for judicious 3-partitions of graphs

Judicious partition problems seek partitions that optimize several quantities simultaneously. A well-known judicious partition problem of Bollob\'{a}s and Scott asks for a $k$-partition $(V_1,\ldots,V_k)$ of a graph that minimizes the number of edges inside each part while maximizing the total number of edges between the parts. Despite considerable efforts, the case when $k=3$ has remained open for the past two decades. In this paper, we resolve this case in a strong sense by proving that every graph with $m$ edges admits a 3-partition $(V_1,V_2,V_3)$ such that

$$\max_{1 \leq i \leq 3} e(V_i) \leq \frac{m}{9} + \frac{1}{9}h(m) \quad \text{and} \quad e(V_1, V_2, V_3) \geq \frac{2}{3}m + \frac{1}{3}h(m),$$

where $h(m)=\sqrt{2m+1/4}-1/2$. This result is tight. We also resolve this problem for general $k$ when $m<2k^2$. We further establish a connection between our result and another judicious partition problem raised by Bollob\'{a}s and Scott. This is joint work with Yan Wang.

In Terms 1 and 2, the seminar was organised by Jun Gao and Oleg Pikhurko.

Term 2

16th Jan: Max Kölbl, The University of Osaka

Symmetric edge polytopes and Ehrhart polynomial roots

The study of roots of Ehrhart polynomials goes back to a paper by Bump, Choi, Kurlbeck, and Vaaler (2000) in the context of number theory. They noticed that cross-polytopes have their Ehrhart polynomial roots on the canonical line (CL), i.e. the line in ℂ with real part -1/2. I will introduce the class of symmetric edge polytopes -- a generalisation of cross-polytopes --, a conjecture pertaining to the CL-ness of on, and methods and results that have sprung from investigating this still wide open conjecture.

23th Jan: Zhuo Wu, Universitat Politècnica de Catalunya

Iterated Cantor--Bendixson Derivatives of the Set of Hypergraph Tur\'an Densities

Let $\Pi^{(k)}\subset[0,1]$ denote the set of Tur\'an densities of single $k$-uniform hypergraphs. While for graphs ($k=2$) the set of Tur\'an densities is discrete, the hypergraph case ($k\ge 3$) exhibits a much richer and still poorly understood structure. Motivated by the ``no-jump'' phenomenon (and the contrast with families of hypergraphs), recent work showed that $\Pi^{(k)}$ already has accumulation points for every $k\ge 3$.

In this talk we push this viewpoint to higher order via the Cantor--Bendixson derivative. Writing $A(S)$ for the set of accumulation points of a subset $S\subset\mathbb{R}$ and defining $A^{m}(S)$ iteratively, we prove that for every integer $k\ge 3$ and every $m\in\mathbb{N}$, the iterated derivative $A^{m}(\Pi^{(k)})$ is non-empty; equivalently, $\Pi^{(k)}$ contains limit points of every finite Cantor--Bendixson rank. The talk will start by recalling the original construction and guiding ideas of Conlon--Sch\"ulke, and then explain how we extend their framework to obtain these higher-order accumulation phenomena.

This work is joint with David Conlon, Ander Lamaison, Hong Liu, and Bjarne Sch\"ulke.

30th Jan: Antonio Girao, University College London

Cycles with almost linearly many chords

Chen, Erdős, and Staton asked in 1996 how many edges are required in an $n$-vertex graph to guarantee a cycle with as many chords as vertices. The best current bound, due to Draganić, Methuku, Munhá Correia, and Sudakov shows that average degree $(\log n)^{8}$ already suffices.

In this talk, I will show that constant average degree is enough to guarantee a cycle on $l$ vertices with at least $\Omega\left(\frac{l}{\log^{C}(l)}\right)$ chords. This answers a question of Dvořák, Martins, Thomassé, and Trotignon asking whether constant-degree graphs must contain cycles whose chord counts grow with their length. This is joint work with Nemanja Draganić.

6th Feb: Minmin Wang, University of Sussex

Colour ratio in Prim’s ranking of the complete bipartite graph

We consider the complete bipartite graph with n black vertices and m=an white vertices, equipped with i.i.d Uniform (0, 1) weights. The minimum spanning tree of the weighted graph can be found using the so-called Prim’s Algorithm, which outputs a sequence of increasing subtrees T_k, where T_k is a bipartite tree of k vertices. Denote by rho_k the ratio of white vs black vertices in T_k. In a joint work with Félix Kahane, we give a complete characterisation of the asymptotic behaviours of rho_k as both k and n tend to infinity (possibly with different speeds). In particular, our result implies that unless m=n or k=m+n, the colour ratio we observe in T_k converges to a quantity different from m/n=a.

13th Feb: Tung H. Nguyen, University of Oxford

Polynomial χ-boundedness for excluding the five-vertex path

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.

20th Feb: Daniel Kráľ, Leipzig University and MPI MiS

Quasirandomness through lenses of combinatorial limits

A combinatorial object is said to be quasirandom if it resembles a random object in a certain robust sense. The notion of quasirandom graphs, which was developed in the work of Rödl, Thomason, Chung, Graham and Wilson in the 1980s, appears in fundamental concepts in modern combinatorics such as the Regularity Method of Szemerédi. The notion is particularly robust as several different properties of truly random graphs, e.g., subgraph density, edge distribution and spectral properties, are satisfied by a large graph if and only if one of them is.

We will present classical and recent results on quasirandomness of different combinatorial objects, in particular, graphs, directed graphs, permutations, hypergraphs and Latin squares. We will demonstrate how analytic methods provided by the theory of combinatorial limits, which we introduce during the talk, can be used to obtain results concerning quasirandom combinatorial objects. We will also explore the relation of presented results to other areas of mathematics, particularly, highlighting the link to the stochastic block model in statistics.

27th Feb: Agelos Georgakopoulos, University of Warwick

On better-quasi-ordering under graph minors

The celebrated Graph Minor Theorem of Robertson & Seymour states that the finite graphs are well-quasi-ordered (WQO) under the minor relation. Well-known remaining open problems ask whether they are better-quasi-ordered (BQO), and whether the countably infinite graphs are WQO.

We connect these problems as follows: we prove that the finite graphs are WQO iff the countably infinite graphs with no infinite paths are WQO iff the latter are BQO. We provide further equivalent statements and side results. No prior knowledge of BQO theory or infinite graph theory is assumed.

6th March: Johannes Carmesin, TU Freiberg

The hidden two-dimensional structure of graph separations

Term 1

10th Oct: Julia Böttcher, The London School of Economics and Political Science

Robustness and resilience for spanning graph of bounded degree

The well-known conjecture of Bollob\'as, Eldridge, and Catlin states that any $n$-vertex graph with minimum degree of $(1-\frac{1}{\Delta+1})n$ contains any $n$-vertex graph with maximum degree $\Delta$ as a subgraph. This remains open, but the best general condition for all $\Delta$ is still given by a classic theorem of Sauer and Spencer. We prove sparse analogues of this theorem.

In the talk I will provide some background to this problem, survey developments in the past decades and explain what kind of sparse analogues we obtain, which ingredients go into the proofs (spreadness, and the sparse blow-up lemma, among others) and what remains open.

17th Oct: Eoin Hurley, University of Oxford

Path Factors of Regular Graphs and Linear Arboricity

7th Nov: Jeck Lim, University of Oxford

Sums of algebraic dilates