The Combinatorics, Probability and Algorithms seminar is usually held weekly during termtime.
Tuesday 20 January 2026, 13:00-14:00
Watson Building, Lecture Theatre B
Let $Q^n$ be the $n$-dimensional binary hypercube. We consider a random subgraph $Q^n_p$ of the hypercube formed by retaining each edge of $Q^n$ independently with probability $p$. Like the binomial random graph $G(n,p)$, this model undergoes a striking phase-transition when $p$ increases beyond the critical value of $1/n$. However, whilst the structure of $G(n,p)$ in this supercritical regime is well understood, much less is known about the structure of $Q^n_p$.
Confirming a long-standing folklore conjecture, stated in particular by Condon, Espuny Díaz, Girão, Kühn, and Osthus, we show that for any constant $\epsilon >0$ there is a $C:=C(\epsilon)$ such that if $p= C/n$, then with high probability $Q^n_p$ contains a path covering all but an $\epsilon$-fraction of its vertices.
This is joint work with Sahar Diskin, Joshua Erde, Mihyun Kang, Michael Krivelevich and Lyuben Lichev.
Tuesday 27 January 2026, 13:00-14:00
Watson Building, Lecture Theatre B
A derangement is a permutation with no fixed points. Whenever a permutation group acts transitively it contains a derangement. This result, usually attributed to Jordan, is an easy application of the orbit-counting lemma. There are now many generalisations of this result, with much more sophisticated proofs. In this talk, I will discuss connections between these and various topics in combinatorics, such as the Erdos-Ko-Rado Theorem in extremal combinatorics, the Polycirculant Conjecture in graph theory and Isbell's Conjecture on fair games.
Tuesday 3 February 2026, 13:00-14:00
Watson Building, Lecture Theatre B
Rota's basis conjecture from 1989 asserts that, given any $n$ bases $B_1, \ldots , B_n$ of a vector space of dimension $n$ (or, more generally, a matroid of rank $n$), there is a collection of $n$ disjoint transversal bases. In other words, the elements of $B_1, \ldots , B_n$ can be decomposed into $n$ new bases of the vector space (or matroid), each consisting of exactly one element from each of the original bases $B_1, \ldots , B_n$.
In this talk, I will discuss some progress towards this conjecture which shows that, in this setting, $(1-o(1))n$ disjoint transversal bases always exist and that the union of the bases $B_1, \ldots , B_n$ can be covered by $(1+o(1))n$ transversal bases.
This is joint work with Lisa Sauerman.
Tuesday 10 February 2026, 13:00-14:00
Watson Building, Lecture Theatre B
Abstract: TBA
Tuesday 24 February 2026, 13:00-14:00
Watson Building, Lecture Theatre B
Abstract: TBA
Tuesday 3 March 2026, 13:00-14:00
Watson Building, Lecture Theatre B
Abstract: TBA
Tuesday 10 March 2026, 13:00-14:00
Watson Building, Lecture Theatre B
Abstract: TBA
Tuesday 17 March 2026, 13:00-14:00
Watson Building, Lecture Theatre B
Abstract: TBA
Friday 27 March 2026, 15:30-16:30
Poynting, Lecture Theatre S06 (Small)
Abstract: TBA
Tuesday 28 April 2026, 13:00-14:00
Watson Building, Lecture Theatre B
Abstract: TBA
Thursday 2 October 2025, 13:00-14:00
Watson Building, B16
Given a poset $P$, a family $\mathcal F$ of points in the Boolean lattice is said to be induced-$P$-saturated if (1) $\mathcal F$ contains no copy of $P$ as an induced (i.e., strong) subposet and (2) every strict superset of $\mathcal F$ contains a copy of $P$ as an induced subposet. The minimum size of an induced-$P$-saturated family in the Boolean lattice of dimension $n$ is denoted by $\mathrm{sat}^*(n,P)$.
The notion was introduced by Ferrara, Kay, Kramer, Martin, Reiniger, Smith, and Sullivan (2017) based in part on a previous notion of not-necessarily-induced saturation by Gerbner, Keszegh, Lemons, Palmer, Pálvölgyi, and Patkós (2013), which parallels the deep literature on the saturation function for graphs. Although induced saturation in graphs is not a natural concept, it seems to be particularly natural in the setting of posets.
In this talk, we discuss the classical results and new developments on bounds of $\mathrm{sat}^*(n,P)$ for well-studied posets $P$.
Thursday 9 October 2025, 14:00-15:00
Watson Building, B16
Given an integer $k \ge 1$, an edge-$k$-colouring of a graph $G$ is an assignment of colours $1, \dots, k$ to the edges of $G$ such that no two adjacent edges receive the same colour. A vertex-distinguishing (resp. sum-distinguishing) edge-$k$-colouring of $G$ is an edge-$k$-colouring in which, for every pair of distinct vertices $u$ and $v$, the set (resp. the sum) of colours assigned to the edges incident with $u$ differs from that assigned to the edges incident with $v$.
The vertex-distinguishing chromatic index (resp. sum-distinguishing chromatic index), denoted by $\chi'_{vd}(G)$ (resp. $\chi'_{sd}(G)$), is the minimum integer $k$ such that $G$ admits a vertex-distinguishing (resp. sum-distinguishing) edge-$k$-colouring.
In this talk, we will present some recent progress on vertex-distinguishing and sum-distinguishing edge-colourings of graphs. This work is joint with Songling Shan, Guanghui Wang, and Yiming Zhou.
Thursday 16 October 2025, 13:00-14:00
Watson Building, B16
An $H$-packing in a graph $G$ is a collection of vertex-disjoint copies of $H$. We show that for every constant $c > 0$ and bipartite graph $H$, every $d$-regular $n$-vertex graph with $d > cn$ has an $H$-packing covering all but a constant number of vertices. This resolves a problem by Kühn and Osthus from 2015, and is a joint work with Abhishek Methuku and Benny Sudakov.
Thursday 23 October 2025, 13:00-14:00
Watson Building, B16
Dirac's theorem states that every ($n$-vertex) graph with minimum degree at least $n/2$ contains a Hamilton cycle. A discrepancy version of this theorem, proved by various groups, states that every $r$-colouring of the edges of every graph with minimum degree at least $(1/2 + 1/2r + o(1))n$ contains a Hamilton cycle where one of the colours appears at least $(1 + o(1))n / r$ times. We generalise this result by asymptotically determining the maximum possible value $f_{r,\alpha}(n)$ for every $\alpha \geq 1/2$ such that every $r$-colouring of the edges of every graph with minimum degree at least $\alpha n$ contains a Hamilton cycle where one of the colours appears at least $f_{r, \alpha}(n)$ times.
Lee and Sudakov extended Dirac's theorem to the setting of random graphs by showing that a random graph (above the threshold to contain a Hamilton cycle) typically has the property that every spanning subgraph with minimum degree at least $(1/2+o(1))np$ contains a Hamilton cycle. We show that such a random graph typically satisfies that every $r$-colouring of the edges of every spanning subgraph with minimum degree at least $\alpha n$ contains a Hamilton cycle where one of the colours appears at least $f_{r, \alpha}(n)$ times. This is asymptotically optimal and strengthens a result of Gishboliner, Krivelevich and Michaeli.
In this talk I will share some of the ideas behind our proofs. This is joint work with Natalie Behague and Debsoumya Chakraborti.
Thursday 30 October 2025, 13:00-14:00
Watson Building, B16
A classic result in extremal combinatorics is Dirac's theorem, which states that any graph on $n$ vertices with minimum degree $n/2$ has a Hamilton (i.e. spanning) cycle. In 1995, Komlós, Sárközy and Szemerédi showed that if the minimum degree is at least $2n/3$, then there is a square of a Hamilton cycle. (A square of a Hamilton cycle is a graph with vertices $v_1, v_2, v_3, \dots, v_n$ such that any three consecutive vertices (modulo $n$) form a triangle. In this talk, we discuss its extension to hypergraphs, in particular, to $3$-uniform hypergraphs.
This is joint work with Allan Lo and Richard Mycroft.
Thursday 6 November 2025, 13:00-14:00
Watson Building, B16
In 2023, Frankl, Pach, and Pálvölgyi introduced new set families called odd-sunflowers, a variation of sunflowers as originally studied by Erdős and Rado, and posed the question of finding the maximal set families on $[n]$ which contain no odd-sunflower. In pursuit of answering this question we introduced the concept of t-temperate set families — a set family is $t$-temperate if for any of its members, the number of its subsets inside the set family is at most the number of its subsets of size at most $t$ — motivated by the fact that odd-sunflower-free set families are necessary $1$-temperate and intersecting.
The main results presented in this talk describe the maximal $t$-temperate set families on $[n]$ and, for odd $n$, also the maximal intersecting $t$-temperate set families. Both results are proved using probabilistic techniques analogous to those used in the probabilistic proof of Sperner's theorem. For even $n$, a conjectured maximal $t$-temperate set family called lightning is introduced.
This is joint work with Jan Petr.
Thursday 13 November 2025, 13:00-14:00
Watson Building, B16
Every graph contains a triangle-free subgraph with at least half the edges and, more generally, every graph contains an $H$-free subgraph with at least a $1 - 1/(\chi(H) - 1)$-proportion of the edges. The Mantel, Turán, and Erdős-Stone-Simonovits theorems show that the constants $1/2$ and $1 - 1/(\chi(H) - 1)$ cannot be improved - complete graphs form a family of universal witnesses for this problem.
The corresponding problem for ordered graphs is much more interesting and nuanced. Reiher, Rödl, Sales, and Schacht showed that complete graphs are not universal and determined the correct constant for directed paths. In this talk I will discuss a family of universal witnesses and what we can use them for.
Joint work with Arjun Ranganathan (UCL), Leo Versteegen (Warwick), and Ella Williams (UCL)
Thursday 20 November 2025, 13:00-14:00
Watson Building, B16
We identify an asymptotically best-possible minimum positive codegree condition for the existence of a Hamilton $\ell$-cycle in a $k$-graph. This is a natural extension of Dirac's theorem on Hamilton cycles to the setting of uniform hypergraphs. The talk will also discuss the advantages and drawbacks of minimum positive codegree conditions compared to the more commonly considered minimum codegree conditions in the context of Dirac-type problems in hypergraphs.
Joint work with Camila Zárate-Guerén.
Thursday 27 November 2025, 13:00-14:00
Watson Building, B16
Rödl, Ruciński and Szemerédi found best-possible codegree conditions that force the existence of perfect matchings in $k$-graphs. Given that the codegree is too strong for many applications, we study this question for a weaker, but more versatile degree condition, which maintains the codegree's constructive power: the positive codegree. For a $k$-graph, this corresponds to the minimum degree over all sets of size $k-1$ with degree at least one.
For $k\geq 3$, we show exact minimum positive codegree conditions for the existence of perfect matchings in $k$-graphs with no isolated vertices. Our threshold is best possible and improves a previous result by Halfpap and Magnan.
Thursday 4 December 2025, 13:00-14:00
Watson Building, B16
A graph $G$ is said to be Ramsey for a tree $T$ if every 2-edge colouring of $G$ contains a monochromatic copy of $T$. It is known that for large $n$ the complete graph on $2n-2$ vertices is Ramsey for the class of trees on $n$ vertices. A natural question is whether completeness is necessary. In this direction, Schelp proposed the following question. Let $\Delta \ge 2, \epsilon > 0$ and $n$ large enough. Let $T$ be a tree on $n$ vertices with maximum degree bounded by $\Delta$, and $G$ a graph on $(1 + \epsilon) 2n$ vertices with minimum degree greater than $3|G|/4$. Is $G$ Ramsey for $T$? We prove two stronger versions of Schelp's conjecture: one for trees of constant maximum degree and one for trees of degree bounded by $n^{\alpha}$ for some $\alpha \in (0, 1)$. The proof utilises the regularity method and a stability argument.