Sharp threshold for rigidity of random graphs

DOI10.1112/BLMS.12740zbMATH Open1519.05221arXiv2202.09917MaRDI QIDQ6135068FDOQ6135068

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

Publication date: 23 August 2023

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

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$.

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

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

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)

Cites Work

• Title not available (Why is that?)
• An algorithm for two-dimensional rigidity percolation: The pebble game
• Sudden emergence of a giant \(k\)-core in a random graph
• Pebble game algorithms and sparse graphs
• Generic global rigidity
• On graphs and rigidity of plane skeletal structures
• Title not available (Why is that?)
• Title not available (Why is that?)
• Characterizing generic global rigidity
• Conditions for Unique Graph Realizations
• Paths in graphs
• On Generic Rigidity in the Plane
• The Rigidity of Graphs
• The rigidity of graphs. II
• Title not available (Why is that?)
• Sufficient conditions for the global rigidity of graphs
• Title not available (Why is that?)
• A new approach to the orientation of random hypergraphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• The 2-dimensional rigidity of certain families of graphs
• The Rigidity of Frameworks: Theory and Applications
• Integral homology of random simplicial complexes
• Rigidity Matroids
• The rigidity transition in random graphs
• On rigidity, orientability, and cores of random graphs with sliders
• Rigidity of Random Subgraphs and Eigenvalues of Stiffness Matrices

Cited In (5)

• Maximum likelihood thresholds via graph rigidity
• On the \(d\)-dimensional algebraic connectivity of graphs
• Sharp thresholds for certain Ramsey properties of random graphs
• Reconstructing a point set from a random subset of its pairwise distances
• Edge rigidity and universality of random regular graphs of intermediate degree

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)