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