Sharp thresholds for NAC-colourings and stable cuts in random graphs

Abstract

NAC-colourings of graphs correspond to flexible quasi-injective realisations in ${\mathbb{R}}^2$. A special class of NAC-colourings are those that arise from stable cuts. We give sharp thresholds for the random graph to have no stable cut and to have no NAC-colouring via exact hitting-time results: with high probability, the random graph process gains both properties at the precise time that every vertex is in a triangle. Our thresholds complement recent results on the thresholds for the random graph to be generically or globally rigid in ${\mathbb{R}}^d$, and for all injective realisations to be globally rigid in $\mathbb{R}$.

15 pages