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

2025/10/07 by Katie Clinch, John Haslegrave, Clinch, Katie +5
Computer Science · #Advanced Graph Theory Research

paper · pdf · doi:10.48550/arxiv.2510.05838

Abstract

NAC-colourings of graphs correspond to flexible quasi-injective realisations in \mathbb R ². 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 .

Citations

• On forest and bipartite cuts in sparse graphs
• Stable cuts, NAC-colourings and flexible realisations of graphs
• Extremal Problems on Forest Cuts and Acyclic Neighborhoods in Sparse Graphs
• Forest Cuts in Sparse Graphs
• Reconstructing a point set from a random subset of its pairwise distances
• Determining a Points Configuration from a Subset of the Pairwise Distances
• Sharp threshold for rigidity of random graphs
• Generic Global Rigidity

Related

• Colouring complete bipartite graphs from random lists
• Sharp thresholds for Ramsey properties
• The optimal edge-colouring threshold
• Ramsey games near the critical threshold
• Rigid colourings of hypergraphs and contiguity