Combinatorics Seminar 202324
For 202324, the Combinatorics Seminar will be held 23pm on Fridays in B3.02. In Term 1, the seminar is being organised by Richard Montgomery, Candida Bowtell and Debsoumya Chakraborti. Abstracts will be added below the table when details are available.
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.