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

Term 3

28th June: Nika Salia, King Fahd University

Linear three-uniform hypergraphs with no Berge path of given length

21st June: George Kontogeorgiou, University of Chile

Small weakly separating path systems for complete graphs

14th June: Sean Dewar, University of Bristol

Counting realisations of rigid graphs

7th June: Oliver Janzer, University of Cambridge

Tight general bounds for the extremal numbers of 0-1 matrices

31st May: Katharina Jochemko, Royal Institute of Technology (KTH)

Weighted Ehrhart theory

24th May: Levente Bodnar, University of Oxford

Extremal Problems in Circuit Complexity

15th May: Robert Hancock, University of Oxford

Typical Ramsey properties of the primes and abelian groups

Given a matrix $A$ with integer entries, a subset $S$ of an abelian group and $r\in\mathbb N$, we say that $S$ is $(A,r)$-Rado if any $r$-colouring of $S$ yields a monochromatic solution to the system of equations $Ax=0$. A classical result of Rado characterises all those matrices $A$ such that $\mathbb N$ is $(A,r)$-Rado for all $r \in \mathbb N$. R\"odl and Ruci\'nski, and Friedgut, R\"odl and Schacht proved a random version of Rado’s theorem where one considers a random subset of $[n]:=\{1,\dots,n\}$.

In this paper, we investigate the analogous random Ramsey problem in the more general setting of abelian groups. Given a sequence $(S_n)_{n\in\mathbb N}$ of finite subsets of abelian groups, let $S_{n,p}$ be a random subset of $S_n$ obtained by including each element of $S_n$ independently with probability $p$. We are interested in determining the probability threshold for $S_{n,p}$ being $(A,r)$-Rado.

Our main result is a general black box for hypergraphs which we use to tackle problems of this type. Using this tool in conjunction with a series of supersaturation results, we determine the probability threshold for a number of different cases. A consequence of the Green--Tao theorem is the van der Waerden theorem for the primes: every finite colouring of the primes contains arbitrarily long monochromatic arithmetic progressions. Using our machinery, we obtain a random version of this result. We also prove a novel supersaturation result for $[n]^d$ and use it to prove an integer lattice generalisation of the random version of Rado's theorem.

This is joint work with Andrea Freschi and Andrew Treglown (both University of Birmingham).

3rd May: Martin Winter, University of Warwick

Kalai's 3^d conjecture for coordinate-symmetric polytopes

26th April: Asier Calbet-Ripodas, Queen Mary University of London

The asymptotic behaviour of $sat(n,\mathcal{F})$

Given a family $\mathcal{F}$ of graphs, we say that a graph $G$ is \emph{$\mathcal{F}$-saturated} if it is maximally $\mathcal{F}$-free, meaning $G$ does not contain a graph in~$\mathcal{F}$ but adding any new edge to $G$ creates a graph in~$\mathcal{F}$. We then define $sat(n,\mathcal{F})$ to be the minimum number of edges in an $\mathcal{F}$-saturated graph on $n$ vertices. In 1986, K\'aszonyi and Tuza showed that $sat(n,\mathcal{F})=O(n)$ for all families $\mathcal{F}$ and Tuza conjectured that for singleton families $sat(n,\mathcal{F})/n$ converges. Tuza's Conjecture remains wide open. In this talk, I will discuss recent results about the asymptotic behaviour of $sat(n,\mathcal{F})$, mostly in the sparse regime $sat(n,\mathcal{F}) \leq n+o(n)$, in each of the cases when $\mathcal{F}$ is a singleton, when $\mathcal{F}$ is finite and when $\mathcal{F}$ is possibly infinite. Joint work with Andrea Freschi.

25th April: Jun Gao, Institute for Basic Science (IBS)

Generalized Ramsey--Tur\'an density for cliques

We study the generalized Ramsey--Tur\'an function $\mathrm{RT}(n,K_s,K_t,o(n))$, which is the maximum possible number of copies of $K_s$ in an $n$-vertex $K_t$-free graph with independence number $o(n)$. The case when $s=2$ was settled by Erd{\H{o}}s, S{\'o}s, Bollob{\'a}s, Hajnal, and Szemer\'{e}di in the 1980s. We combinatorially resolve the general case for all $s\ge 3$, showing that the (asymptotic) extremal graphs for this problem have simple (bounded) structures. In particular, it implies that the extremal structures follow a periodic pattern when $t$ is much larger than $s$. Our results disprove a conjecture of Balogh, Liu, and Sharifzadeh and show that a relaxed version does hold. This is a joint work with Suyun Jiang, Hong Liu and Maya Sankar.

Term 2

15th March: Natalie Behague, University of Warwick

The rainbow saturation number

The saturation number of a graph is a famous and well-studied counterpoint to the Turán number, and the rainbow saturation number is a generalisation of the saturation number to the setting of coloured graphs. Specifically, for a given graph $F$, an edge-coloured graph is $F$-rainbow saturated if it does not contain a rainbow copy of $F$, but the addition of any non-edge in any colour creates a rainbow copy of $F$. The rainbow saturation number of $F$ is the minimum number of edges in an $F$-rainbow saturated graph on $n$ vertices. Girão, Lewis, and Popielarz conjectured that, like the saturation number, for all $F$ the rainbow saturation number is linear in $n$. I will present our attractive and elementary proof of this conjecture, and finish with a discussion of related results and open questions.

This is joint work with Tom Johnston, Shoham Letzter, Natasha Morrison and Shannon Ogden.

8th March: Alexandra Wesolek, Technische Universität Berlin

Reconfiguration of plane trees in convex geometric graphs

A reconfiguration graph consists of solutions to a problem, with an edge between two solutions if one solution can be obtained from the other by what is called a flip. This talk focuses on reconfiguration graphs where the vertices i.e. solutions are non-crossing spanning trees of a set of n points in the plane (edges of the tree are drawn as straight lines and none of the edges cross each other). A flip consists of exchanging an edge in a non-crossing spanning tree with another one so that the resulting graph is also a non-crossing spanning tree. Avis and Fukuda proved in 1996 that there always exists a flip sequence of length at most 2n-4 between any pair of non-crossing spanning trees. In a joint work with Nicolas Bousquet, Lucas De Meyer and Théo Pierron, we show that for a convex set of n points there always exists a flip sequence of length at most c n where c is approximately 1.95. This improves the upper bound for convex point sets by a linear factor for the first time in about 30 years.

1st March: Joanna Lada, London School of Economics

Hamilton decompositions of regular tripartite tournaments

Given a Hamiltonian graph $G$, it is natural to ask whether its edge set admits a full decomposition into Hamilton cycles. In the setting of regular oriented graphs, this has been confirmed for sufficiently large regular tournaments (Kühn, Osthus (2013)), bipartite tournaments (Granet (2022)), and $k$-partite tournaments when $k\geq 4$ (Kühn, Osthus (2013)).

For regular tripartite tournaments, a complete decomposition is not always possible; the known counterexample, $\mathcal{T}_\Delta$, consists of the blowup of $C_3$ with a single triangle reversed. However, it is reasonable to think that all such non-decomposable regular tripartite tournaments fall within a specifiable class, and perhaps are even all isomorphic to $\mathcal{T}_\Delta$.

In this talk, we make progress towards this question by proving the approximate result; that is, given a regular tripartite tournament, one can find a decomposition of its edge set into edge-disjoint Hamilton cycles covering all but $o(n^2)$ edges.

Joint work with Francesco Di Braccio, Viresh Patel, Yanitsa Pehova, and Jozef Skokan.

23rd February: William Turner, University of Birmingham

Simultaneously embedding sequences of graphs

Graph embeddability is a well-studied problem in topological combinatorics. Perhaps the most famous result in this field is Kuratowski’s Theorem (1930), which characterises when a graph is planar in terms of forbidden substructures. In recent years, progress has been made characterising different types of embeddability for combinatorial objects of higher dimension. In this talk, we will present a natural way to embed “temporal sequences”, sequences (G1,...,Gn) of graphs where each consecutive pair is related via the minor relation. For a restricted case, we will build up a characterisation in terms of “forbidden sequential minors”. To do so, we will need to develop a theory of abstract duals for temporal sequences, analogous to Whiteny’s Criterion (1932). Finally, we will discuss some wider complexity results and open problems.

16th February: Asier Calbet Ripodas, Queen Mary University of London

The asymptotic behaviour of $sat(n,\mathcal{F})$

Given a family $\mathcal{F}$ of graphs, we say that a graph $G$ is $\mathcal{F}$-saturated if it is maximally $\mathcal{F}$-free, meaning $G$ does not contain a graph in~$\mathcal{F}$ but adding any new edge to $G$ creates a graph in~$\mathcal{F}$. We then define $sat(n,\mathcal{F})$ to be the minimum number of edges in an $\mathcal{F}$-saturated graph on $n$ vertices. In 1986, Kászonyi and Tuza showed that $sat(n,\mathcal{F})=O(n)$ for all families $\mathcal{F}$ and Tuza conjectured that for singleton families $sat(n,\mathcal{F})/n$ converges. Tuza's Conjecture remains wide open. In this talk, I will discuss recent results about the asymptotic behaviour of $sat(n,\mathcal{F})$, mostly in the sparse regime $sat(n,\mathcal{F}) \leq n+o(n)$, in each of the cases when $\mathcal{F}$ is a singleton, when $\mathcal{F}$ is finite and when $\mathcal{F}$ is possibly infinite. Joint work with Andrea Freschi.

9th February: Debsoumya Chakraborti, University of Warwick

This is joint work with Candy Bowtell, Patrick Morris and Yani Pehova, and with Yangyang Cheng.

12th January: Jane Tan, University of Oxford

Reconstructing cube complexes from boundary distances

Given a quadrangulation of a disc, suppose we know all the pairwise distances (measured by the graph metric) between vertices on the boundary of the disc. Somewhat surprisingly, a result of Haslegrave states that this is enough information to recover the whole interior structure of the quadrangulation provided all internal vertex degrees are at least 4. In this talk, we look at a generalisation of this result to 3 dimensions: it is possible to reconstruct 3D cube complexes that are homeomorphic to a ball from the pairwise distances between all points on the boundary sphere provided certain curvature conditions hold. This is joint work with Haslegrave, Scott and Tamitegama. We’ll also survey some related results from before and after our work.

Term 1

6th October: Michael Savery, University of Oxford

Chromatic number is not tournament-local

Scott and Seymour conjectured the existence of a function f such that, for every graph G and tournament T on the same vertex set, \chi(G)\geq f(k) implies that \chi(G[N_T^+(v)])\geq k for some vertex v. We will disprove this conjecture even if v is replaced by a vertex set of size \mathcal{O}(\log{|V(G)|}). As a consequence, we obtain a negative answer to a question of Harutyunyan, Le, Thomassé, and Wu concerning the analogous statement where the graph $G$ is replaced by another tournament. Time permitting, we will also discuss the setting in which chromatic number is replaced by degeneracy, where a quite different behaviour is exhibited.

This is joint work with António Girão, Kevin Hendrey, Freddie Illingworth, Florian Lehner, Lukas Michel, and Raphael Steiner.

13th October: Abhishek Methuku, ETH Zurich

The extremal number of cycles with all diagonals

In 1975, Erdős asked: What is the maximum number of edges that an n-vertex graph can have without containing a cycle with all diagonals? Erdős observed that the upper bound O(n^{5/3}) holds since the complete bipartite graph K_{3,3} can be viewed as a cycle of length six with all diagonals. In this paper, we resolve this problem. We prove that there exists a constant C such that every n-vertex with Cn^{3/2} edges contains a cycle with all diagonals. Since any cycle with all diagonals contains cycles of length four, this bound is best possible using well-known constructions of graphs without a four-cycle based on finite geometry. Among other ideas, our proof involves a novel lemma about finding an `almost-spanning' robust expander which might be of independent interest.

This is joint work with Domagoj Bradač and Benny Sudakov.

20th October: António Girão, University of Oxford

On induced C₄-free graphs with high average degree

A long-standing conjecture of Thomassen fro the 80's states that for every graph with sufficiently high average degree contains a subgraph with high girth and still preserving large enough average degree. This conjecture has only been resolved in the early 2000's by Kühn and Osthus in the first non-trivial case i.e. they showed that for every k, there is f(k) such the every graph with average degree at least $f(k)$ contains a subgraph which is C₄-free with average degree k.

We will talk about a recent result which strengthens this result of Kühn and Osthus in two ways. First, we prove an analogous induced version and secondly we give much better bounds for the function f allowing us obtain few non-trivial results as simple corollaries.

The talk is based on a joint work with Du, Scott, Hunter and McCarty and another with Hunter.

27th October: Yani Pehova, LSE

The Erdős-Rothschild problem for dichromatic triangles

In 1974 Erdős and Rothschild asked the following question: given integers k, s and a large n, what is the maximum number of s-edge-colourings of an n-vertex graph free of a monochromatic k-vertex clique? A follow up question is to determine which graph(s) attain this maximum. Recent work of Pikhurko, Staden and Yilma shows that in most cases this problem reduces to considering complete multipartite graphs and only counting a natural family of Kk-free "template" colourings of their edge set. Despite this reduction, the Erdős-Rothschild problem has only been solved for some small s and k. Various generalisations of this problem have been considered in the literature, where instead of forbidding monochromatic cliques, we forbid other, non-monochromatic, patterns on a clique. We consider the problem of maximising the number of s-edge-colourings without triangles which see exactly two colours, and show that for every s, the extremal graph is an r-partite Turán graphs where r is easy to compute for any given s.

This is joint work with Pranshu Gupta, Emil Powierski and Katherine Staden.

10th November: Tom Johnston, Bristol

Shotgun assembly of random graphs

How much local information is needed to reconstruct a graph? In the graph shotgun assembly problem, we are given the balls of radius r around the vertices of a graph and we are asked to identify the graph. We will consider this problem for the Erdős-Rényi random graph G(n,p) for fixed r and discuss the thresholds on p for when the graph is or is not reconstructible with high probability. In particular, we will give the threshold for each r \geq 3.

17th November: Namrata, University of Warwick

Kneser Graphs are Hamiltonian

For integers k ≥ 1 and n ≥ 2k+1, the Kneser graph K(n,k) has as vertices all k-element subsets of an n-element ground set, and an edge between any two disjoint sets. It has been conjectured since the 1970s that all Kneser graphs admit a Hamilton cycle, with one notable exception, namely the Petersen graph K(5,2). This problem received considerable attention in the literature, including a recent solution for the sparsest case n = 2k + 1. The main contribution of this paper is to prove the conjecture in full generality. We also extend this Hamiltonicity result to all connected generalized Johnson graphs (except the Petersen graph). The generalized Johnson graph J(n,k,s) has as vertices all k-element subsets of an n-element ground set, and an edge between any two sets whose intersection has size exactly s. Clearly, we have K(n,k) = J(n,k,0), i.e., generalized Johnson graph include Kneser graphs as a special case. Our results imply that all known families of vertex-transitive graphs defined by intersecting set systems have a Hamilton cycle, which settles an interesting special case of Lovász’ conjecture on Hamilton cycles in vertex-transitive graphs from 1970. Our main technical innovation is to study cycles in Kneser graphs by a kinetic system of multiple gliders that move at different speeds and that interact over time, reminiscent of the gliders in Conway’s Game of Life, and to analyze this system combinatorially and via linear algebra.

Joint work with Arturo Merino and Torsten Mütze.

24th November: Andrea Freschi, University of Birmingham

Discrepancy in edge-coloured and oriented graphs

Given graphs G and H, what is the largest t such that in any 2-colouring of the edges of G, there is a copy of H in G with at least t edges in the same colour? Note that a 2-edge-coloured copy of H must have at least |E(H)|/2 edges in one colour, so one is interested in whether a colour-bias significantly above this can be achieved.

This topic was first raised by Erdős in the 1960s and has attracted renewed attention in recent years. Several classical results in extremal graph theory have been transferred to this setting, including Dirac's theorem for Hamilton cycles and the Hajnal-Szemerédi theorem for clique factors. In this talk, I will survey some of these results and discuss two variants of the problem for r-edge-coloured graphs and oriented graphs. For these variants, we prove analogues of Dirac's theorem.

This is based on joint works with Joseph Hyde, Joanna Lada, Allan Lo and Andrew Treglown.

1st December: Kyriakos Katsamaktsis, UCL

Ascending subgraph decomposition

We prove for large graphs the following conjecture of Alavi, Boals Chartrand, Erdős and Oellermann from 1987: any graph with (m+1)m/2 edges can be decomposed into graphs G_1,...,G_m such that G_i has exactly i edges and is isomorphic to a subgraph of G_{i+1}.

This is joint work with Shoham Letzter, Alexey Pokrovskiy and Benny Sudakov.

8th December: Martin Ryan, Iowa State

Counting cycles in planar graphs

Basic Tur\'an theory asks how many edges a graph can have, given certain restrictions such as not having a large clique. A more generalized Tur\'an question asks how many copies of a fixed subgraph H the graph can have, given certain restrictions. There has been a great deal of recent interest in the case where the restriction is planarity. In this talk, we will discuss some of the general results in the field, primarily the asymptotic value of N_{\mathcal P}(n,H), which denotes the maximum number of copies of H in an n-vertex planar graph. In particular, we will focus on the case where $H$ is a cycle. It was determined that N_{\mathcal P}(n,C_{2m})=(n/m)^m+o(n^m) for small values of m by Cox and Martin and resolved for all m by Lv, Gy\H{o}ri, He, Salia, Tompkins, and Zhu. The case of H=C_{2m+1} is more difficult and it is conjectured that N_{\mathcal P}(n,C_{2m+1})=2m(n/m)^m+o(n^m). We will discuss recent progress on this problem, including verification of the conjecture in the case where m=3 and m=4 and a lemma which reduces the solution of this problem for any m to a so-called ``maximum likelihood'' problem. The maximum likelihood problem is, in and of itself, an interesting question in random graph theory.

This is joint work with Emily Heath and Chris (Cox) Wells.