Rödl and Ruciński [Threshold functions for Ramsey properties, J. Amer. Math. Soc. 8 (1995)] established Ramsey's theorem for random graphs. In particular, for fixed integers r and ℓ ≥ 2 they showed that ˆpkℓ,r(n) = n-2/ℓ+1 is a threshold for the Ramsey property that every r-colouring of the edges of the binomial random graph G(n,p) yields a monochromatic copy of Kℓ. We investigate how this result extends to arbitrary colourings of G(n,p) with an unbounded number of colours. In this situation, Erdős and Rado [A combinatorial theorem, J. London Math. Soc. 25 (1950)] showed that canonically coloured copies of Kℓ can be ensured in the deterministic setting. We transfer the Erdős-Rado theorem to the random environment and show that both thresholds coincide when ℓ ≥ 4. As a consequence, the proof yields Kℓ+1-free graphs G for which every edge colouring contains a canonically coloured Kℓ. The 0-statement of the threshold is a direct consequence of the corresponding statement of the Rödl-Ruciński theorem and the main contribution is the 1-statement. The proof of the 1-statement employs the transference principle of Conlon and Gowers [Combinatorial theorems in sparse random sets, Ann. of Math. (2) 184 (2016)].

A graph $G$ is Ramsey for a graph $H$ if every 2-coloring of the edges of $G$ contains a monochromatic copy of $H$. We consider the following question: if $H$ has bounded treewidth, is there a “sparse” graph $G$ that is Ramsey for $H$? Two notions of sparsity are considered. Firstly, we show that if the maximum degree and treewidth of $H$ are bounded, then there is a graph $G$ with $O(|V(H)|)$ edges that is Ramsey for $H$. This was previously only known for the smaller class of graphs $H$ with bounded bandwidth. On the other hand, we prove that in general the treewidth of a graph $G$ that is Ramsey for $H$ cannot be bounded in terms of the treewidth of $H$ alone. In fact, the latter statement is true even if the treewidth is replaced by the degeneracy and $H$ is a tree.

A subset $S$ of initially infected vertices of a graph $G$ is called zero forcing if we can infect the entire graph by iteratively applying the following process. At each step, any infected vertex which has a unique uninfected neighbor, infects this neighbor. The zero forcing number of $G$ is the minimum cardinality of a zero forcing set in $G$. We study the zero forcing number of various classes of graphs, including graphs of large girth, $H$-free graphs for a fixed bipartite graph $H$, and random and pseudorandom graphs.