Combinatorics Seminar 2023-24
For 2023-24, the Combinatorics Seminar will be held 2-3pm 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 tournament-local |
|
| 13th Oct | Abhishek Methuku | The extremal number of cycles with all diagonals | |
| 20th Oct | 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.