The celebrated canonical Ramsey theorem of Erdős and Rado implies that for a given graph H, if n is sufficiently large then any colouring of the edges of Kn gives rise to copies of H that exhibit certain colour patterns, namely monochromatic, rainbow or lexicographic. We are interested in sparse random versions of this result and the threshold at which the random graph G(n,p) inherits the canonical Ramsey properties of Kn. Our main result here pins down this threshold when we focus on colourings that are constrained by some prefixed lists. This result is applied in an accompanying work of the authors on the threshold for the canonical Ramsey property (with no list constraints) in the case that H is an even cycle.

An (n, d, λ)-graph is an n vertex, d-regular graph with second eigenvalue in absolute value λ. When λ is small compared to d, such graphs have pseudorandom properties and make good expander graphs. A fundamental question in the study of pseudorandom graphs is to find conditions on the parameters that guarantee the existence of a certain subgraph. A celebrated construction due to Alon gives a triangle-free (n, d, λ)-graph with d = Θ(n2/3) and λ = Θ(d2/n). This construction is optimal as having λ = o(d2/n) guarantees the existence of a triangle in an (n, d, λ)-graph. Krivelevich, Sudakov and Szabó (2004) conjectured that if n ∊ 3ℕ and λ = o(d2/n) then an (n, d, λ)-graph G in fact contains a triangle factor: vertex disjoint triangles covering the whole vertex set. This conjecture has attracted the attention of many authors but until now has evaded a full solution. In this paper1, we confirm the conjecture of Krivelevich, Sudakov and Szabó and our proof gives a randomised algorithm that finds a triangle factor. The result can be seen as a clear distinction between pseudorandom graphs and random graphs, showing that essentially the same pseudorandom condition that ensures a triangle in a graph actually guarantees a triangle factor. In fact, even more is true: as a corollary to this result and a result of Han, Kohayakawa, Person and the author, we can conclude that the same condition actually guarantees that such a graph G contains every graph on n vertices with maximum degree at most 2.

We investigate the emergence of spanning structures in sparse pseudo-random k-uniform hypergraphs, using the following comparatively weak notion of pseudorandomness. A k-uniform hypergraph H on n vertices is called (p, α, ε)-pseudo-random if for all not necessarily disjoint sets A1, …, Ak ⊂ V (H) with |A1|···|Ak| > αnk we have e(A1, …, Ak) = (1 ± ε)p|A1|···|Ak|. For any linear k-uniform F we provide a bound on α = α(n) in terms of p = p(n) and F, such that (under natural divisibility assumptions on n) any (p, α, o(1))-pseudo-random n-vertex H with a mild minimum degree condition contains an F-factor. The approach also enables us to establish the existence of loose Hamilton cycles in sufficiently pseudo-random hypergraphs and all results imply corresponding bounds for stronger notions of hypergraph pseudo-randomness such as jumbledness or large spectral gap. As a consequence of our results, perfect matchings appear at α = o(pk) while loose Hamilton cycles appear at α = o(pk–1). This extends the works of Lenz–Mubayi, and Lenz–Mubayi–Mycroft who studied the analogous problems in the dense setting.