Sharp threshold for rigidity of random graphs

DOI10.1112/BLMS.12740MaRDI QIDQ6135068zbMATH OpenFDO

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)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

Erdős-Rényi evolution of random graphsinfinitesimal rigidity

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Random graphs (graph-theoretic aspects) (05C80) 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

• 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
• 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?)
• 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 \(k\)-orientability thresholds for \(G_{n,p}\)
• The 2-dimensional rigidity of certain families of graphs
• 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
• The rigidity of graphs. II
• The rigidity transition in random graphs

Cited in

(13)

• Edge rigidity and universality of random regular graphs of intermediate degree
• Sharp thresholds for certain Ramsey properties of random graphs
• On rigidity, orientability, and cores of random graphs with sliders
• Rigidity of random subgraphs and eigenvalues of stiffness matrices
• The rigidity transition in random graphs
• On the \(d\)-dimensional algebraic connectivity of graphs
• Maximum likelihood thresholds via graph rigidity
• Reconstructing a point set from a random subset of its pairwise distances
• Reconstructing almost all of a point set in \(\mathbb{R}^d\) from randomly revealed pairwise distances
• Global rigidity of random graphs in \({\mathbb{R}}\)
• Minimum degree conditions for graph rigidity
• Generic global rigidity in _p-space and the identifiability of the p-Cayley-Menger varieties
• Rigid partitions: from high connectivity to random graphs

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)