Combinatorics Seminar

For 2024-25, the Combinatorics Seminar will be held 2-3pm on Fridays in B3.02, unless otherwise stated.

In Term 2, the seminar is organised by Natalie Behague, Debsoumya Chakraborti, Agelos Georgakopoulos and Richard Montgomery. Abstracts will be added below the table when details are available.

Term 2

Date	Name	Title	Note
10th Jan	Xizhi Liu	An invitation to the density Hajnal--Szemer\'{e}di problem
17th Jan	Julian Sahasrabudhe	A new lower bound for sphere packing
24th Jan	Bobby Miraftab	Infinite Cycles in Cayley Graphs and Eigenvectors of Finite Support
31st Jan	Agelos Georgakopoulos	A survey of coarse graph theory
7th Feb	Sayan Mukherjee	Spectral graph clustering and local differential privacy
14th Feb	Marc Distel	Further improvements to the product structure extension of the Alon-Seymour-Thomas theorem
19th Feb	Karim Adiprasito	(Open) Extremal problems in combinatorics and algebra	3-4pm B1.01 (Wednesday)
21st Feb	Sandra Albrechtsen	Asymptotic and diverging half- and full-grid minors
28th Feb	Nora Frankl	The Quantitative Helly Theorem
7th March	Andrew Treglown	Arbitrary orientations of Hamilton cycles in directed graphs
11th March	Maksim Zhukovskii	The sharp threshold for the square of a Hamilton cycle	3-4pm B3.02 (Tuesday)
14th March	Shoham Letzter	Almost covering regular graphs by F-subdivisions

10th Jan: Xizhi Liu, Warwick

An invitation to the density Hajnal--Szemer\'{e}di problem

The problem of determining the minimum degree threshold that guarantees a graph on

$n$ vertices contains a collection of

$k$ vertex-disjoint copies of a certain graph

$F$ is quite well understood, thanks to decades of effort by numerous researchers, starting from foundational work by Corr\'{a}di--Hajnal (1963) and Hajnal--Szemer\'{e}di (1970).

In contrast, the analogous problem of determining the average degree threshold is less explored, even though Erd\H{o}s had already attempted the triangle case in the 1960s.

In this talk, we will survey related results/open problems and discuss some recent progress on this topic.

17th Jan: Julian Sahasrabudhe, Cambridge

A new lower bound for sphere packing

What is the maximum proportion of d-dimensional space that can be covered by disjoint, identical spheres? In this talk I will discuss a new lower bound for this problem, which is the first asymptotically growing improvement to Rogers' bound from 1947. Our proof is almost entirely combinatorial and reduces to a novel theorem about independent sets in graphs with bounded degrees and codegrees.

This is based on joint work with Marcelo Campos, Matthew Jenssen and Marcus Michelen.

24th Jan: Bobby Miraftab, Carleton University

Infinite Cycles in Cayley Graphs and Eigenvectors of Finite Support

This talk has two parts. In the first part, we explore infinite cycles in Cayley graphs. A weaker version of the celebrated Lovász conjecture asserts that every finite, connected Cayley graph contains a hamiltonian cycle. While infinite graphs cannot possess hamiltonian cycles in the traditional sense, there are natural analogues. We focus on a topological approach to this problem, demonstrating how some results for finite Cayley graphs can be extended to the infinite case. Additionally, we propose some open questions. In the second part, we turn our attention to constructions of locally finite graphs with eigenvectors of finite support, particularly for "very symmetric" graphs and over finite fields. We will provide some background, present basic constructions yielding "somewhat symmetric" examples, and discuss obstructions that preclude certain potential examples.

31st Jan: Agelos Georgakopoulos, Warwick

A survey of coarse graph theory

I will survey results and open questions on 'coarse graph theory', an emerging area that combines ideas from graph theory and coarse geometry.

7th Feb: Sayan Mukherjee, University of Tokyo

Spectral graph clustering and local differential privacy

Finding clusters in graphs is an important problem in social network analysis. Of the many ways of finding such clusters, spectral clustering is widely used for the ease of implementation and its approximation guarantees via the Cheeger inequalities. However, simply publishing information about clusters in a social network leads to leakage in privacy. In a locally differentially private graph algorithm, users locally perturb their adjacency data before sending it to a central server, which then makes some inference on the perturbed graph. With proper addition of noise, it can be possible to protect users' privacy while still making statistical inference about the underlying social networks. In this talk, we will analyze the robustness of the spectral clustering algorithm under the addition of noise in the adjacency information.

14th Feb: Marc Distel, Monash University

Further improvements to the product structure extension of the Alon-Seymour-Thomas theorem

Alon, Seymour, and Thomas [1990] showed that every $n$ vertex graph that excludes $K_t$ as a minor has treewidth and pathwidth at most $O_t(\sqrt{n})$ . Distel, Dujmović, Eppstein, Hickingbotham, Joret, Micek, Morin, Seweryn, and Wood [2024] expanded on this, showing that these graphs could be written as a $O_t(\sqrt{n})$ -blowup of a treewidth 4 graph. I further refine this, by showing that the treewidth 4 can be replaced by treewidth 3, and can be further reduced to pathwidth 2 if you allow the blowup to have size $O_t(\sqrt{n}\log(n)^2)$ .

19th Feb: Karim Adiprasito, Jussieu Institute of Mathematics - Paris Rive Gauche

(Open) Extremal problems in combinatorics and algebra

Algebraic combinatorics and extremal combinatorics are, sadly, almost disjoint. Algebraic combinatorics deals with isomorphisms, and is an exact science. Extremal combinatorics is a study of a more quantitative nature. Hence, marrying the two is difficult. I will outline several problems that attempt to quantify "algebraic" results and present some results and open problems. This talk is more of a challenge with many open problems rather than results :)

21st Feb: Sandra Albrechtsen, Hamburg University

Asymptotic and diverging half- and full-grid minors

Georgakopoulos and Hamann [2024] showed that every locally finite, quasi-transitive graph $G$ that is not quasi-isometric to a tree contains the full-grid as a minor.

In this talk I discuss how this result could be strengthened so that the full-grid minor appears in the coarse (`large-scale') geometry of $G$ . For this, I define asymptotic minors and diverging minors and describe how the full-grid can be found as such minors in $G$ if $G$ has the additional property that its cycle space is generated by cycles of bounded length. In particular, it follows that all locally finite Cayley graphs of finitely presented groups that are not virtually free contain the full-grid as an asymptotic minor and as a diverging minor.

Additionally, I discuss assumptions which ensure that a (not necessarily quasi-transitive) graph contains the half-grid as an asymptotic minor and as a diverging minor.

This is based on joint work with Matthias Hamann.

28th Feb: Nora Frankl, Open University

The Quantitative Helly Theorem

Helly's theorem states that if the intersection of any d+1 members of a finite family F of convex sets in R^d is nonempty, then the intersection of the whole family is nonempty. The Fractional Helly theorem of Katchalski and Liu, and the Quantitative Helly theorem of Bárány, Katchalski, and Pach are two famous extensions of this result. Improving on several recent works, we prove an optimal combination of these two extensions. We show that if a positive fraction of the (d+1)-tuples of F intersect in large volume, then a positive fraction of F intersects in large volume as well. Joint work with Attila Jung and Istvan Tomon.

7th March: Andrew Treglown, University of Birmingham

Arbitrary orientations of Hamilton cycles in directed graphs

In 1960, Ghouila-Houri proved that every strongly connected directed graph G on n vertices and with minimum degree at least n contains a directed Hamilton cycle. We asymptotically generalize this result by proving the following: every directed graph G on n vertices and with minimum degree more than (1+o(1))n contains every orientation of a Hamilton cycle, except for the directed Hamilton cycle in the case when G is not strongly connected.

This is joint work with Louis DeBiasio.

11th March: Maksim Zhukovskii, University of Sheffield

The sharp threshold for the square of a Hamilton cycle

In 2020, Kahn, Narayanan, and Park conjectured that the probability threshold for the binomial random graph G(n,p) to contain the square of a Hamilton cycle is (1+o(1))\sqrt{e/n}. In the talk, I will present a proof of this conjecture. Although the proof relies on the fragmentation technique, as the original proof by Kahn, Narayanan and Park for establishing a coarse threshold, the way of selecting fragments is essentially different. One of the main ingredients of the proof is the fact that sufficiently many squares of cycles have fragments that avoid squares of paths of length at least logarithmic in n with high probability.

14th March: Shoham Letzter, University College London

Almost covering regular graphs by F-subdivisions

A conjecture of Verstraëte from 2002 asserts that for every graph F there exists d such that every regular graph with degree at least d has a collection of pairwise vertex-disjoint subdivisions of F covering almost all the vertices in the graph. We prove this conjecture for regular n-vertex graphs with degree at least (log n)^{130}. Along the way we develop useful tools related to almost regular expanders.

This is joint work with Abhishek Methuku and Benny Sudakov.

In Term 1, the seminar was organised by Natalie Behague, Debsoumya Chakraborti and Richard Montgomery.

Term 1

Date	Name	Title
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$ .