Skip to main content Skip to navigation

Combinatorics Seminar

For 2023-24, the Combinatorics Seminar will be held 2-3pm 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 Brunn-Minkowski 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 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

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 $|i-j|\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 graph-collection $\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 edge-disjoint 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, Bermond-Fouquet-Habib-Peroche, Wormald, Jackson-Wormald, Fouquet-Thuillier-Vanherpe-Wojda). 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 Brunn-Minkowski 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 Brunn-Minkowski inequality. In the discrete world, A and B must additionally posses a lattice-like structure as described by Freiman-Ruzsa 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 n-vertex 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 tournament-local


13th Oct Abhishek Methuku The extremal number of cycles with all diagonals  
20th Oct

António Girão

On induced C4-free graphs with high average degree  
27th Oct Yani Pehova The Erdős-Rothschild 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 edge-coloured 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 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 C4-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 C4-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.