The Combinatorics, Probability and Algorithms seminar is usually held weekly during termtime.
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.