Combinatorics Seminar

For 2024-25, the Combinatorics Seminar will be held 2-3pm on Fridays in B3.02. In Term 1, the seminar is organised by Natalie Behague, Debsoumya Chakraborti and Richard Montgomery. Abstracts will be added below the table when details are available.

Term 1

Date	Name	Title	Note
4th Oct	Akshat Mudgal	Approximating sumset estimates via translates
11th Oct	Ella Williams	Covering vertices with monochromatic paths
18th Oct	Camila Zárate-Guerén	Colour-bias perfect matchings in hypergraphs
25th Oct	Sarah Selkirk	Directed lattice paths with negative boundary
1st Nov	Marius Tiba	Upper bounds for multicolour Ramsey numbers
8th Nov	Matias Pavez-Signe	Ramsey numbers of cycles in random graphs
15th Nov	Brett Kolesnik	Graphical sequences and plane trees
22nd Nov	Maria Ivan	Euclidean Ramsey sets and the block sets conjecture
29th Nov	Peleg Michaeli	Extremal and probabilistic aspects of graph rigidity
6th Dec	Debmalya Bandyopadhyay	Monochromatic tight cycle partitions in edge-coloured complete $k$-graphs

4th Oct: Akshat Mudgal, University of Warwick

Approximating sumset estimates via translates

A finite, non-empty subset A of Z^d is defined to be d-dimensional if it is not contained in a translate of some hyperplane. Given a d-dimensional set A of cardinality N, a classical result in additive combinatorics known as Freiman’s lemma implies that

|A+A| >= (d+1)N - d(d+1)/2.

Moreover, this estimate is sharp.

In the spirit of some recent work of Bollobas–Leader–Tiba, it is natural to ask whether one can approximate this lower bound by just considering a few translates of A. In joint work with Yifan Jing we prove precisely this, that is, for any d-dimensional set A with N elements, there exists a subset X of A with |X| = O_d(1) such that

|A+X| >= (d+1)N - d(d+1)/2.

11th Oct: Ella Williams, UCL

Covering vertices with monochromatic paths

Abstract: In 1995, Erd\H{o}s and Gy\'arf\'as proved that in every 2-edge-coloured complete graph on $n$ vertices, there exists a collection of $2\sqrt{n}$ monochromatic paths, all of the same colour, which cover the entire vertex set. They conjectured that it is possible to replace $2\sqrt{n}$ by $\sqrt{n}$. We prove this to be true for all sufficiently large $n$.

This is based on joint work with Alexey Pokrovskiy and Leo Versteegen.

18th Oct: Camila Zárate-Guerén, University of Birmingham

Colour-bias perfect matchings in hypergraphs

Given a k-uniform hypergraph H on n vertices with an r-colouring of its edges, we look for a minimum l-degree condition that guarantees the existence of a perfect matching in H that has more than n/rk edges in one colour. We call this a colour-bias perfect matching.

For 2-coloured graphs, a result of Balogh, Csaba, Jing and Pluhár yields the minimum degree threshold that ensures a perfect matching of significant colour-bias. In this talk, I will present an analogous of this result for k-uniform hypergraphs. More precisely, for each 1<=l<k and r>=2 we determined the minimum l-degree threshold that forces a perfect matching of significant colour-bias in an r-edge-coloured k-uniform hypergraph.

The presented result is joint work with J. Balogh, H. Hàn, R. Lang, J. P. Marciano, M. Pavez-Signé, N. Sanhueza-Matamala and A. Treglown.

25th Oct: Sarah Selkirk, University of Warwick

Directed lattice paths with negative boundary

Given a set $\mathcal{S} \subseteq \{1\}\times \mathbb{Z}$, a directed lattice path with stepset $\mathcal{S}$ is a finite sequence whose elements are in $\mathcal{S}$. Visually, the elements of the sequence are drawn as vectors starting at $(0, 0)$. Further restrictions, or a lack thereof, on the height of $y$-coordinates ($y\geq 0$) and end-point ($y=0$) of the sequence result in a classification of paths into the four main varieties of lattice path: walks, bridges, meanders, and excursions. For these families, generating functions have been derived in general in the influential work of Banderier and Flajolet (2002) by means of the kernel method. In recent years, directed lattice paths with height restriction $y \geq -t$ with $t\in \mathbb{N}$ have been connected to a number of other combinatorial objects, but have not yet been studied in general. In this talk, we discuss first enumerative results towards a general Banderier-Flajolet-style result for paths with a negative boundary.

1st Nov: Marius Tiba, King's College London

Upper bounds for multicolour Ramsey numbers

The $r$-colour Ramsey number $R_r(k)$ is the minimum $n \in \mathbb{N}$ such that every $r$-colouring of the edges of the complete graph $K_n$ on $n$ vertices contains a monochromatic copy of $K_k$. We prove, for each fixed $r \geqslant 2$, that $$R_r(k) \leqslant e^{-\delta k} r^{rk}$$ for some constant $\delta = \delta(r) > 0$ and all sufficiently large $k \in \mathbb{N}$. For each $r \geqslant 3$, this is the first exponential improvement over the upper bound of Erd\H{o}s and Szekeres from 1935. In the case $r = 2$, it gives a different proof of a recent result of Campos, Griffiths, Morris and Sahasrabudhe. This is based on joint work with Paul Balister, B\'ela Bollob\'as, Marcelo Campos, Simon Griffiths, Eoin Hurley, Robert Morris and Julian Sahasrabudhe.

8th Nov: Matias Pavez-Signe, University of Chile

Ramsey numbers of cycles in random graphs

Let C_n denote the cycle on n vertices. We say a graph G is C_n-Ramsey if every 2-colouring of the edges of G contains a monochromatic copy of C_n. The classical Ramsey problem for cycles asks for determining the minimum number R(C_n) so that the complete graph on R(C_n) vertices is C_n-Ramsey. This talk will study when a random graph G(N,p) is C_n-Ramsey with high probability. In particular, we will show that even for very sparse edge probability p and N quite close to R(C_n), G(N,p) remains C_n-Ramsey.

15th Nov: Brett Kolesnik, University of Warwick

Graphical sequences and plane trees

We show that the asymptotic number of graphical sequences can be expressed in terms of Walkup’s formula for the number of plane trees. This yields a more detailed description of the asymptotics by Balister, Donderwinkel, Groenland, Johnston and Scott. Our proof is probabilistic, using what we call the Lévy–Khintchine method. We will discuss other applications of this method, and connections with additive number theory (subset counting formulas by von Sterneck and the Erdös–Ginzburg–Ziv theorem). Joint work with Michal Bassan (Oxford) and Serte Donderwinkel (Groningen).

22nd Nov: Maria Ivan, University of Cambridge

Euclidean Ramsey sets and the block sets conjecture

A set $X$ is called Euclidean Ramsey if, for any $k$ and sufficiently large $m$, any $k$-colouring of $\mathbb{R}^m$ contains a monochromatic congruent copy of $X$. This notion was introduced by Erd\H{o}s, Graham, Montgomery, Rothschild, Spencer and Straus. They asked if a set is Ramsey if and only if it is spherical, meaning that it lies on the surface of a sphere. It is not too difficult to show that if a set is not spherical, then it is not Euclidean Ramsey either, but the converse is very much open despite extensive research over the years. On the other hand, the block sets conjecture is a purely combinatorial, Hales-Jewett type of statement. It was introduced in 2010 by Leader, Russell and Walters. If true, the block sets conjecture would imply that every transitive set (a set whose symmetry group acts transitively) is Euclidean Ramsey. Similarly to the first question, the block sets conjecture remains very elusive. In this talk we discuss recent developments on the block sets conjecture and their implications to Euclidean Ramsey sets.

Joint work with Imre Leader and Mark Walters.

29th Nov: Peleg Michaeli, University of Oxford

Extremal and probabilistic aspects of graph rigidity

Combinatorial rigidity theory addresses questions such as: given a structure defined by geometric constraints, what can be inferred about its geometric behaviour based solely on its underlying combinatorial data? Such structures are often modelled as assemblies of rigid rods connected by rotational joints, in which case the underlying combinatorial data is a graph. A typical question in this context is: given such a framework in generic position in R^d, is it rigid? That is, does every continuous motion of the vertices (joints) that preserves the lengths of all edges (rods) necessarily preserve the distances between all pairs of vertices?

In this talk, I will present new sufficient conditions for the rigidity of a framework in R^d based on the notion of rigid partitions - partitions of the underlying graph that satisfy certain connectivity properties. I will outline several broadly applicable conditions for the existence of such partitions and discuss a few applications, among which are new results on the rigidity of highly connected and (pseudo)random graphs.

If time allows, I will also discuss new - often sharp - sufficient minimum degree conditions for d-dimensional rigidity and mention a related novel result on the pseudoachromatic number of graphs.

The talk is based on joint works with Michael Krivelevich and Alan Lew.

6th Dec: Debmalya Bandyopadhyay, University of Birmingham

Monochromatic tight cycle partitions in edge-coloured complete $k$-graphs

Let $K_n^{(k)}$ be the complete $k$-uniform hypergraph on $n$ vertices. A tight cycle is a $k$-uniform graph with its vertices cyclically ordered so that every~$k$ consecutive vertices form an edge, and any two consecutive edges share exactly~$k-1$ vertices. A result by Bustamante, Corsten, Frankl, Pokrovskiy and Skokan shows that all $r$-edge coloured $K_{n}^{(k)}$ can be partition into $c_{r,k}$ vertex disjoint monochromatic tight cycles. However, the constant $c_{r,k}$ is of tower-type. In this work, we show that $c_{r,k}$ is a polynomial in~$r$.