Combinatorics Seminar

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

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

Date	Name	Title	Note
10th Oct	Julia Böttcher	Robustness and resilience for spanning graph of bounded degree
17th Oct	Eoin Hurley	Path Factors of Regular Graphs and Linear Arboricity
24th Oct	Nemanja Draganić	Hamilton cycles in pseudorandom graphs: resilience and approximate decompositions
7th Nov	Jeck Lim	Sums of algebraic dilates
14th Nov	Natalie Behague	On random regular graphs and the Kim-Vu Sandwich Conjecture
21th Nov	Ritesh Goenka	Source localisation in random walks and internal DLA
28th Nov	Vadim Lozin	Hereditary properties of graphs
5th Dec	Leo Versteegen	All in on R(m,d): the universally optimal host graph for the relative ordered Tur\'{a}n problem
12th Dec	Mingyuan Rong	On codegree Turán density of tight cycles

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

Graph Decomposition problems have seen huge progress in recent years. However most of this progress has been confined to the dense regime.

For example, the linear arboricity conjecture concerns the decomposition of bounded degree graphs into unions of vertex disjoint paths. The conjecture originated in 1980 with Akiyama, Exoo, and Harary and was resolved asymptotically by Alon in the 1990's. However, in spite of much attention an exact resolution remains far away. Indeed, even the problem of finding a single path factor of the correct size was wide open. We find path factors in regular graphs of the correct size (up to a factor of 2) and use this to generate a new kind of bound for the Linear Arboricity Problem.

This talk is based on joint work with Micha Christoph, Nemanja Draganić, António Girão, Lukas Michel, and Alp Müyesser.

24th Oct: Nemanja Draganić, University of Oxford

Hamilton cycles in pseudorandom graphs: resilience and approximate decompositions

Dirac’s theorem says that every graph with minimum degree at least half the number of its vertices has a Hamilton cycle. In recent decades, attention has turned to whether similar results hold for sparse pseudorandom graphs, which behave like random graphs in their edge distribution but are defined deterministically.

In this talk, I will describe new results giving an optimal version of Dirac’s theorem in this pseudorandom setting. We show that mildly pseudorandom graphs remain Hamiltonian even after deleting about half the edges at each vertex. Moreover, for a d-regular pseudorandom graph, not only does a Hamilton cycle exist, but the graph almost decomposes into them, containing roughly (1 − ε)d / 2 edge-disjoint Hamilton cycles.

7th Nov: Jeck Lim, University of Oxford

Sums of algebraic dilates

In this talk, we answer the above problem in the following general form: if $\lambda_1,\ldots,\lambda_k$ are algebraic numbers, then

$$|A+\lambda_1\cdot A+\dots+\lambda_k\cdot A|\geq H(\lambda_1,\ldots,\lambda_k)|A|-o(|A|)$$

for all finite subsets $A$ of $\mathbb{C}$, where $H(\lambda_1,\ldots,\lambda_k)$ is an explicit constant that is best possible. We will discuss the main tools used in the proof, which include a Frieman-type structure theorem for sets with small sums of dilates, and a high-dimensional notion of density which we call "lattice density". Joint work with David Conlon.

14th Nov: Natalie Behague, University of Warwick

On random regular graphs and the Kim-Vu Sandwich Conjecture

The random regular graph G_d(n) is selected uniformly at random from all d-regular graphs on n vertices. This model is a lot harder to study than the Erdős-Renyi binomial random graph model G(n, p) as the probabilities of edges being present are not independent. Kim and Vu conjectured that when d ≫ log n it is possible to ‘sandwich’ the random regular graph G_d(n) between two Erdős-Renyi random graphs with similar edge density. A proof of this sandwich conjecture would unify many previous separate hard-won results.

Various authors have proved weaker versions of the sandwich conjecture with incrementally improved bounds on d — the previous state of the art was due to Gao, Isaev and McKay who proved the conjecture for d ≫ (log n)^4. I will sketch our new proof of the full conjecture.

This is joint work with Richard Montgomery and Daniel Il'kovič.

21th Nov: Ritesh Goenka, University of Oxford

Source localisation in random walks and internal DLA

Suppose we observe the final growth cluster of a random growth process, can we reliably recover where it started? We consider this question for the (edge or vertex) trace of the simple random walk on vertex transitive graphs. As we shall see, the answer seems to be closely related to the transience of the random walk. For the simple random walk on $\mathbb{Z}^d$, we obtain almost optimal bounds on the probability of correctly identifying the source as $d$ goes to infinity. We will also discuss some variants of the problem, including localisation from an infinite trace and a high accuracy version. Finally, we shall discuss analogous questions and results for internal diffusion limited aggregation (IDLA) on $\mathbb{Z}^d$. This talk is based on joint work with Peter Keevash and Tomasz Przybyłowski.

28th Nov: Vadim Lozin, University of Warwick

Hereditary properties of graphs

The world of hereditary properties (also known as hereditary classes) is rich and diverse. It contains a variety of properties of theoretical or practical importance, such as planar, bipartite, perfect graphs, etc. Thousands of results in the literature are devoted to individual classes and only a few of them analyse the universe of hereditary classes as a whole. In this talk, we focus on results that reveal a structure in this family and on classes that play a critical role in this structure.

5th Dec: Leo Versteegen, University of Warwick

All in on R(m,d): the universally optimal host graph for the relative ordered Tur\'{a}n problem.

For two ordered graphs $F$ and $G$, define $\rho_<(F,G)$ as the greatest density of an $F$-free subgraph of $G$. The relative Tur\'{a}n density $\rho_<(F)$ of is the infimum of $\rho_<(F,G)$ over all host graphs $G$.

Reiher, R\"{o}dl, Sales, and Schacht initiated the study of relative Tur\'{a}n densities of ordered graphs and showed that it is more subtle and interesting than the unordered case. In particular, $\rho_<(F)$ is only known for a handful of graphs. In this talk, I will present out result that there exists a family of graphs $R(m,d)$ such that for all F, whatever value $\rho_<(F)$ may take, that value is achieved by the family $R(m, d)$ as host graphs. I will also discuss some related results on the value of $\rho_<(F)$ for certain families of ordered graphs $F$.

12th Dec: Mingyuan Rong, University of Science and Technology of China

On codegree Turán density of tight cycles

For a $k$-uniform hypergraph $F$, the codegree Turán density $\gamma(F)$ is the supremum over all $\alpha$ such that there exist arbitrarily large $n$-vertex $F$-free $k$-graphs in which every $(k-1)$-subset of vertices is contained in at least $\alpha n$ edges. In this talk, we investigate the codegree Turán density of the $k$-uniform tight cycle $C_l^k$. A construction by Han, Lo, and Sanhueza-Matamala yields a lower bound of $1/p$ for $\gamma(C_l^k)$, where $p$ is the smallest prime factor of $k/\gcd(k,l)$, and they asked whether this bound is tight. We answer this question by establishing a general upper bound and improved constructions, showing that the bound is tight for $p=3$ but not always tight for $p > 3$. Moreover, we determine the exact densities for both the tight cycle and the tight cycle minus an edge for a large class of parameters. This talk is based on joint work with Jie Ma.