The rigidity transition in random graphs

MaRDI QIDQ5365113zbMATH OpenFDO

Authors Shiva Prasad Kasiviswanathan, Cristopher Moore, Louis Theran

Publication date 29 September 2017

Full work available at URL https://arxiv.org/abs/1010.3605, http://dl.acm.org/citation.cfm?id=2133130

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: As we add rigid bars between points in the plane, at what point is there a giant (linear-sized) rigid component, which can be rotated and translated, but which has no internal flexibility? If the points are generic, this depends only on the combinatorics of the graph formed by the bars. We show that if this graph is an Erdos-Renyi random graph G(n,c/n), then there exists a sharp threshold for a giant rigid component to emerge. For c < c_2, w.h.p. all rigid components span one, two, or three vertices, and when c > c_2, w.h.p. there is a giant rigid component. The constant c_2 approx 3.588 is the threshold for 2-orientability, discovered independently by Fernholz and Ramachandran and Cain, Sanders, and Wormald in SODA'07. We also give quantitative bounds on the size of the giant rigid component when it emerges, proving that it spans a (1-o(1))-fraction of the vertices in the (3+2)-core. Informally, the (3+2)-core is maximal induced subgraph obtained by starting from the 3-core and then inductively adding vertices with 2 neighbors in the graph obtained so far.

Recommendations

• On rigidity, orientability, and cores of random graphs with sliders
• Sharp threshold for rigidity of random graphs
• Sudden emergence of a giant k-core in a random graph
• Rigidity of random subgraphs and eigenvalues of stiffness matrices
• The Evolution of Random Graphs

Cited in

(10)

• Edge rigidity and universality of random regular graphs of intermediate degree
• The cavity method for the rigidity transition
• On rigidity, orientability, and cores of random graphs with sliders
• Rigidity of random subgraphs and eigenvalues of stiffness matrices
• Generic unlabeled global rigidity
• Sharp threshold for rigidity of random graphs
• Maximum likelihood thresholds via graph rigidity
• Reconstructing a point set from a random subset of its pairwise distances
• Global rigidity of random graphs in \({\mathbb{R}}\)
• Rigid partitions: from high connectivity to random graphs

This page was built for publication: The rigidity transition in random graphs

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