Sharp threshold for rigidity of random graphs

DOI10.1112/BLMS.12740MaRDI QIDQ6135068zbMATHFDO

Authors Alan Lew, Eran Nevo, Yuval Peled, Orit E. Raz

Publication date 23 August 2023

Published in Bulletin of the London Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2202.09917

zbMATH Keywords

infinitesimal rigidityErdős-Rényi evolution of random graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Planar graphs; geometric and topological aspects of graph theory (05C10) Rigidity and flexibility of structures (aspects of discrete geometry) (52C25)

Abstract: We consider the ErdH{o}s-R'enyi evolution of random graphs, where a new uniformly distributed edge is added to the graph in every step. For every fixed $dge1$, we show that with high probability, the graph becomes rigid in $mathbb{R}^d$ at the very moment its minimum degree becomes $d$, and it becomes globally rigid in $mathbb{R}^d$ at the very moment its minimum degree becomes $d+1$.

Recommendations

• The rigidity transition in random graphs
• Rigidity of random subgraphs and eigenvalues of stiffness matrices
• The 2-dimensional rigidity of certain families of graphs
• Minimally globally rigid graphs
• On rigidity, orientability, and cores of random graphs with sliders

Cites work

• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 3943863 (Why is no real title available?)
• scientific article; zbMATH DE number 480232 (Why is no real title available?)
• scientific article; zbMATH DE number 501471 (Why is no real title available?)
• scientific article; zbMATH DE number 1542661 (Why is no real title available?)
• A new approach to the orientation of random hypergraphs
• An algorithm for two-dimensional rigidity percolation: The pebble game
• Characterizing generic global rigidity
• Conditions for Unique Graph Realizations
• Generic global rigidity
• Integral homology of random simplicial complexes
• On Generic Rigidity in the Plane
• On graphs and rigidity of plane skeletal structures
• On rigidity, orientability, and cores of random graphs with sliders
• Paths in graphs
• Pebble game algorithms and sparse graphs
• Rigidity Matroids
• Rigidity of random subgraphs and eigenvalues of stiffness matrices
• Sudden emergence of a giant \(k\)-core in a random graph
• Sufficient conditions for the global rigidity of graphs
• The 2-dimensional rigidity of certain families of graphs
• The Rigidity of Graphs
• The \(k\)-orientability thresholds for \(G_{n,p}\)
• The random graph threshold for \(k\)-orientiability and a fast algorithm for optimal multiple-choice allocation
• The rigidity of frameworks: theory and applications
• The rigidity of graphs. II
• The rigidity transition in random graphs

Cited in

(8)

• Maximum likelihood thresholds via graph rigidity
• Rigidity of random subgraphs and eigenvalues of stiffness matrices
• On rigidity, orientability, and cores of random graphs with sliders
• Sharp thresholds for certain Ramsey properties of random graphs
• Edge rigidity and universality of random regular graphs of intermediate degree
• On the \(d\)-dimensional algebraic connectivity of graphs
• The rigidity transition in random graphs
• Reconstructing a point set from a random subset of its pairwise distances

This page was built for publication: Sharp threshold for rigidity of random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6135068)