A subgraph of an edge-coloured graph is called rainbow if all its edges have distinct colours. The study of rainbow subgraphs goes back to the work of Euler on Latin squares. This talk will be about proving that every properly edge-coloured complete graph has a rainbow copy of every nearly spanning tree. We will also discuss applications of this result to several problems in graph theory. In particular that conjectures of Ringel and Graham-Sloane hold asymptotically.

This is joint work with Richard Montgomery and Benny Sudakov.

The Erdős-Hajnal Theorem asserts that non-universal graphs, that is, graphs that do not contain an induced copy of some fixed graph H, have homogeneous sets of size significantly larger than one can generally expect to find in a graph. We obtain two results of this flavor in the setting of r-uniform hypergraphs.

1. A theorem of Rödl asserts that if an n-vertex graph is non-universal then it contains an almost homogeneous set (i.e. one with edge density either very close to 0 or 1) of size Ω(n). We prove that if a 3-uniform hypergraph is non-universal then it contains an almost homogeneous set of size Ω(log n). An example of Rödl from 1986 shows that this bound is tight.

2. Let R_r(t) denote the size of the largest non-universal r-graph G so that neither G nor its complement contain a complete r-partite subgraph with parts of size t. We prove an Erdős-Hajnal-type stepping-up lemma, showing how to transform a lower bound for R_r(t) into a lower bound for R_r+1(t). As an application of this lemma, we improve a bound of Conlon-Fox-Sudakov by showing that R₃(t) ≥ t^ct.

Joint work with M. Amir and A. Shapira.

In a two-colouring of the edges of the complete graph on the natural numbers, what is the densest monochromatic infinite path that we can always find? We measure the density of a path by the upper asymptotic density of its vertex set. This question was first studied by Erdös and Galvin, who proved that the best density is between 2/3 and 8/9. In this talk we settle this question by proving that we can always find a monochromatic path of upper density at least (12+√8)/17=0.87226…, and constructing a two-colouring in which no denser path exists.

This represents joint work with Jan Corsten, Louis DeBiasio and Richard Lang.

A well known conjecture of Ryser states that every r-partite hypergraph H has a vertex cover of size at most (r - 1) ν(H), where ν(H) is the matching number of H. In recent years, hypergraphs meeting this conjectured bound have been studied extensively. In particular, it was proved by Haxell, Narins and Szabó that for r = 3 all such hypergraphs with ν > 1 are essentially obtained by taking disjoint copies of intersecting extremal hypergraphs. Abu-Khazneh showed that such a characterisation is false for r = 4 by giving a computer-generated counterexample.

We construct a new family of extremal r-partite hypergraphs (with ν = 2), for r - 1 equal to a prime power q ≥ 5, whose vertex set cannot be partitioned into two sets such that on both of these parts we have an intersecting r-Ryser subhypergraph. We will also discuss some new finite geometric near-extremal constructions for Ryser's conjecture.

Abstract to follow.

The clique chromatic number of a graph G = (V,E) is the minimum number of colors in a vertex coloring so that no maximal (with respect to containment) clique is monochromatic. We prove that the clique chromatic number of the binomial random graph G(n,1/2) is, with high probability, of asymptotic order logarithmic in n.

Joint work with Noga Alon.

Given an n-vertex pseudorandom graph G and a potential 2-factor H (that is, a union of disjoint cycles whose lengths sum to n), we wish to find a copy of H in G, i.e. an embedding φ: V(H) → V(G) so that φ(u)φ(v) ∈ E(G) for all uv ∈ E(H). Particular instances of this problem include finding a triangle-factor and finding a Hamilton cycle in G.

In this talk, after giving the relevant context and history in this field, we will sketch how to find a given H in any suitably pseudorandom graph G. The graphs we will consider will be (n,d,λ) graphs i.e. n vertex d-regular graphs whose second eigenvalue in absolute value is λ. Our condition λ = O(d²/(n log n)) is within a log factor from being tight and provides a positive answer to a recent question of Nenadov (arXiv:1805.09710).

This represents joint work with Jie Han, Yoshiharu Kohayakawa and Yury Person.

Obtaining an efficient bound for the triangle removal lemma is one of the most outstanding open problems of extremal combinatorics. Perhaps the main bottleneck for achieving this goal is that triangle-free graphs can be highly unstructured. For example, triangle-free graphs might have only regular partitions (in the sense of Szemerédi) of tower-type size. And indeed, essentially all the graph properties P for which removal lemmas with reasonable bounds were obtained, are such that every graph satisfying P has a small regular partition. So in some sense, a barrier for obtaining an efficient removal lemma for property P was having an efficient regularity lemma for graphs satisfying P.

In this work we consider the property of being induced C₄-free, which also suffers from the fact that a graph might satisfy this property but still have only regular partitions of tower-type size. By developing a new approach for this problem we manage to overcome this barrier and thus obtain a merely exponential bound for the induced C₄ removal lemma. We thus obtain the first efficient removal lemma that does not rely on an efficient version of the regularity lemma. This is the first substantial progress on a problem raised by Alon in 2001, and more recently by Alon, Conlon and Fox.

Joint work with Asaf Shapira.

For a finite family ℑ of fixed graphs let R_k(ℑ) be the smallest integer n for which every k-coloring of the edges of the complete graph K_n yields a monochromatic copy of some F ∈ ℑ. We say that ℑ is k-nice if for every graph G with χ(G)=R_k(ℑ) and for every k-coloring of E(G) there exists a monochromatic copy of some F ∈ ℑ. It is easy to see that if ℑ contains no forest, then it is not k-nice for any k. It seems plausible to conjecture that a (weak) converse holds, namely, for any finite family of graphs ℑ that contains at least one forest, and for all k ≥ k₀(ℑ) (or at least for infinitely many values of k), ℑ is k-nice.

We prove several (modest) results in support of this conjecture, showing, in particular, that it holds for each of the three families consisting of two connected graphs with 3 edges each.

We say a graph G is Ramsey for a pair of graphs (H₁, H₂) if any red-/blue-colouring of E(G) contains either a red H₁ or a blue H₂. Much research has been devoted to determining the thresholds at which the Erdős-Rényi random graph G(n,p) becomes Ramsey for (H₁, H₂). In this talk, we instead consider the perturbed random graph model, where one sprinkles some random edges on top of a deterministic dense graph, and ask how much less randomness is needed to ensure the resulting graph is Ramsey.

This line of research was initiated by Krivelevich, Sudakov and Tetali in 2006, who determined the thresholds for the pairs (K₃, K_t) with t ≥ 3. Here we extend their work, considering pairs of larger cliques. We also present results for cycles, and cycles versus cliques.

This is joint work with Andrew Treglown.