Аннотация:
Given graphs $G$ and $H$ and an integer $r \ge 2$, we write $G \to (H)_r$ if every $r$-colouring of the edges of $G$ contains contains a monochromatic copy of $H$. It follows from Ramsey's theorem that, when $n$ is sufficiently large, $G \to (H)_r$ is a nontrivial, monotone property of subgraphs $G$ of $K_n$. The celebrated work of Rödl and Ruciński from the 1990s located the threshold for this property in the binomial random graph $G_{n,p}$ for all $H$ and $r.$ We prove that this threshold is sharp when $H$ is a clique or a cycle, for every number of colours $r$; this extends earlier results of Friedgut, Rödl, Ruciński, and Tetali and of Schacht and Schulenburg.
This is joint work with Ehud Friedgut, Eden Kuperwasser, and Mathias Schacht.