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
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
Given a complex number $\lambda$ and a finite set $A$ of complex numbers, how small can the size of the sum of dilate $A + \lambda\cdot A$ be in terms of $|A|$? If $\lambda$ is transcendental, then $|A + \lambda\cdot A|$ grows superlinearly in $|A|$, whereas if $\lambda$ is algebraic, then $|A + \lambda\cdot A|$ only grows linearly in $|A|$. There have been several works in recent years to prove optimal linear bounds in the algebraic case.
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.
