Combinatorics Seminar
For 202324, the Combinatorics Seminar will be held 23pm on Fridays in B3.02. In Term 2, the seminar is 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 2
Date  Name  Title  Note 
12th Jan  Jane Tan  Reconstructing cube complexes from boundary distances  
19th Jan  Katherine Staden  Colourful Hamilton cycles  
26th Jan  Peter van Hintum  Additive Structure; the BrunnMinkowski inequality and beyond.  11am B3.03 
2nd Feb  Gal Kronenberg  Partitioning graphs into isomorphic linear forests  
9th Feb  Debsoumya Chakraborti  Bandwidth theorem for graph transversals  
16th Feb  Asier Calbet Ripodas  The asymptotic behaviour of $sat(n,\mathcal{F})$  postponed 
23rd Feb  William Turner  Simultaneously embedding sequences of graphs  
1st March  Joanna Lada  Hamilton decompositions of regular tripartite tournaments  
8th March  Alexandra Wesolek  Reconfiguration of plane trees in convex geometric graphs  
15th March  Natalie Behague  The rainbow saturation number 
15th March: Natalie Behague, University of Warwick
The rainbow saturation number
The saturation number of a graph is a famous and wellstudied 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 edgecoloured graph is $F$rainbow saturated if it does not contain a rainbow copy of $F$, but the addition of any nonedge 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 noncrossing 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 noncrossing spanning tree with another one so that the resulting graph is also a noncrossing spanning tree. Avis and Fukuda proved in 1996 that there always exists a flip sequence of length at most 2n4 between any pair of noncrossing 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 nondecomposable 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 edgedisjoint 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 wellstudied 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
Bandwidth theorem for graph transversals
The bandwidth of a graph is the minimum $b$ such that there is a labeling of the vertex set of $H$ by the numbers $1,2,\ldots,n$ with $ij\le b$ for every edge $ij$ of $H$. The celebrated bandwidth theorem states that if $H$ is an $n$vertex graph with chromatic number $r$, bounded maximum degree, and bandwidth $o(n)$, then every $n$vertex graph with minimum degree at least $\left(1\frac{1}{r}+o(1)\right)n$ contains a copy of $H$. This minimum degree is best possible up to the $o(1)$ term.
Recently, there have been systematic studies extending spanning subgraph problems to the setting of transversals over a collection of graphs. Given a graphcollection $\mathcal{G}=\{G_1,\dots, G_h\}$ with the same vertex set $V$, an $h$edge graph $H$ on the vertex set $V$ is a $\mathcal{G}$transversal if there exists a bijection $\lambda : E(H) \rightarrow \{1,\ldots,h\}$ such that $e\in E(G_{\lambda(e)})$ for each $e\in E(H)$. The minimum degree condition $\delta(\mathcal{G})=\min\{ \delta(G_i)\}$ for finding a spanning $\mathcal{G}$transversal $H$ have been actively studied when $H$ is a Hamilton cycle, an $F$factor, a tree with maximum degree $o(n/\log n)$, and power of Hamilton cycles, etc.
Generalizing both these results and the original bandwidth theorem, we obtain asymptotically sharp minimum degree conditions for graphs with bounded degree, sublinear bandwidth, and given chromatic number, proving the bandwidth theorem for graph transversals. This talk is based on joint work with Seonghyuk Im, Jaehoon Kim, and Hong Liu.
2nd February: Gal Kronenberg, University of Oxford
Partitioning graphs into isomorphic linear forests
The linear arboricity of a graph G, denoted by la(G), is the minimum number of edgedisjoint linear forests (i.e. collections of disjoint paths) in G whose union is all the edges of G. It is known that the linear arboricity of every cubic graph is 2. In 1987 Wormald conjectured that every cubic graph with even number of edges, can be partitioned such that the two parts are isomorphic linear forests. This is known to hold for Jeager graphs and for some further classes of cubic graphs (see, BermondFouquetHabibPeroche, Wormald, JacksonWormald, FouquetThuillierVanherpeWojda). In this talk we will present a proof of Wormald's conjecture for all large connected cubic graphs.
This is joint work with Shoham Letzter, Alexey Pokrovskiy, and Liana Yepremyan.
26th January: Peter van Hintum, University of Oxford
Additive Structure; the BrunnMinkowski inequality and beyond.
We’ll explore additive structure in continuous and discrete settings, i.e. the question of what structure subsets A and B of a group (in particular R^k and Z) must display if their Minkowski sum A+B is small. In the continuous world, A and B must look similar and almost convex as described by stability results for the BrunnMinkowski inequality. In the discrete world, A and B must additionally posses a latticelike structure as described by FreimanRuzsa type results. In this talk, we’ll consider both perspectives and the connection between them.
This talk is based on various papers joint with Alessio Figalli, Peter Keevash, and Marius Tiba among others.
19th January: Katherine Staden, Open University
Colourful Hamilton cycles
A classical question in graph theory is to find sufficient conditions which guarantee that a graph G contains a Hamilton cycle. A colourful variant of this problem has graphs G_1, ..., G_s on the same nvertex set, where we think of each graph as having a different colour, and we want to find a Hamilton cycle coloured with 1, ..., s whose colouring is from some given list of allowed colourings. I will discuss a selection of results on this problem.
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
Date  Name  Title  Note 
6th Oct  Michael Savery  Chromatic number is not tournamentlocal 

13th Oct  Abhishek Methuku  The extremal number of cycles with all diagonals  
20th Oct  On induced C_{4}free graphs with high average degree  
27th Oct  Yani Pehova  The ErdősRothschild problem for dichromatic triangles  
3rd Nov    
10th Nov  Tom Johnston  Shotgun assembly of random graphs  
17th Nov  Namrata  Kneser Graphs are Hamiltonian  
24th Nov  Andrea Freschi  Discrepancy in edgecoloured and oriented graphs  
1st Dec  Kyriakos Katsamaktsis  Ascending subgraph decomposition  
8th Dec  Ryan Martin  Counting cycles in planar graphs 
6th October: Michael Savery, University of Oxford
Chromatic number is not tournamentlocal
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 nvertex 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 nvertex 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 wellknown constructions of graphs without a fourcycle based on finite geometry. Among other ideas, our proof involves a novel lemma about finding an `almostspanning' 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_{4}free graphs with high average degree
A longstanding 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 nontrivial 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_{4}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 nontrivial 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ősRothschild 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 sedgecolourings of an nvertex graph free of a monochromatic kvertex 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 Kkfree "template" colourings of their edge set. Despite this reduction, the ErdősRothschild 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, nonmonochromatic, patterns on a clique. We consider the problem of maximising the number of sedgecolourings without triangles which see exactly two colours, and show that for every s, the extremal graph is an rpartite 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ősRé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 kelement subsets of an nelement 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 kelement subsets of an nelement 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 vertextransitive graphs defined by intersecting set systems have a Hamilton cycle, which settles an interesting special case of Lovász’ conjecture on Hamilton cycles in vertextransitive 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 edgecoloured and oriented graphs
Given graphs G and H, what is the largest t such that in any 2colouring 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 2edgecoloured copy of H must have at least E(H)/2 edges in one colour, so one is interested in whether a colourbias 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 HajnalSzemerédi theorem for clique factors. In this talk, I will survey some of these results and discuss two variants of the problem for redgecoloured 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 nvertex 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 socalled ``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.