糖心TV

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.

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

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鈥檚 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鈥檚 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 糖心TV

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

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

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