The rigidity transition in random graphs

Shiva Prasad Kasiviswanathan, Cristopher Moore, Louis Theran

Abstract

As rigid bars are added between points in a plane, a critical threshold is reached where a giant rigid component emerges. This component, while capable of rotation and translation, possesses no internal flexibility. For generic points, this transition depends solely on the combinatorics of the underlying graph. We demonstrate that for an Erdős-Rényi random graph $G(n, c/n)$, a sharp threshold for the emergence of a giant rigid component exists at $c_2 \approx 3.588$, coinciding with the threshold for 2-orientability. Furthermore, we prove that this giant component spans nearly the entirety of the (3+2)-core, a specific subgraph defined by its connectivity properties.

Introduction

The study of mechanical rigidity in networks is a fundamental problem in both physics and mathematics, modeling how materials transition from fluid-like to solid-like states. In a 2D plane, connecting points with rigid bars fixes the distances between them. As bars are added randomly, the system eventually transforms from a "floppy" collection of small clusters into a single, massive rigid structure.

Decomposition of graphs into rigid components, illustrating the non-local nature of rigidity.

A primary challenge in analyzing this transition is that rigidity is a non-local property. Adding a single bar in one region can instantly "lock" thousands of distant vertices. While numerical simulations have long suggested the existence of a sharp phase transition, providing a rigorous mathematical proof remained elusive until this work.

Methods

To formalize the rigidity transition, we employ several combinatorial and probabilistic tools:

  1. Maxwell-Laman Theorem: This theorem allows us to treat rigidity as a combinatorial counting problem. A graph is minimally rigid if it contains $2n-3$ edges and every subset of $n'$ vertices contains at most $2n'-3$ edges.
  2. 2-Orientability: We establish a link between rigidity and the ability to orient graph edges such that each vertex has an out-degree of at most 2. This property is mathematically more tractable than direct geometric rigidity.
  3. The (3+2)-Core: We identify the (3+2)-core as the structural foundation of the giant rigid component. It is defined as the maximal induced subgraph obtained by starting with the 3-core and inductively adding vertices that have at least two neighbors already present in the core.
The Henneberg I move (H. I) illustrates the inductive addition of a vertex with two neighbors, a key process in forming the (3+2)-core.
  1. Differential Equations: We analyze the size of the rigid component by modeling a 2-orientation algorithm as a system of differential equations, allowing us to track the "branching process" of rigidity as edges are added to the network.

Key Results and Insights

Our analysis reveals that the rigidity transition is not gradual but occurs at a precise sharp threshold.

  • The $c_2$ Threshold: The transition occurs at $c_2 \approx 3.588$. Below this average degree, rigid components are limited to sizes of one, two, or three vertices. Above this threshold, a giant rigid component spanning a constant fraction of the network emerges.
  • Rigidity vs. Connectivity: The rigidity transition occurs significantly later than the connectivity transition. While a graph becomes connected at an average degree of $c=1$, it requires $c \approx 3.588$ to achieve large-scale rigidity.
  • Structural Dominance: For $c > c_2$, the giant rigid component spans a $(1 - o(1))$-fraction of the (3+2)-core. This confirms that once the transition occurs, the rigid component effectively incorporates almost all potentially rigid structures within the graph.

Discussion and Future Work

This work provides the first rigorous proof for the rigidity transition in random graphs, confirming numerical simulations from the physics literature (e.g., Rivoire and Barré, 2006). However, several open questions remain:

  • Generic Geometry: Our results assume "generic" point positions. Specific geometric arrangements, such as grids or symmetric layouts, may exhibit different behaviors.
  • Global Rigidity: While we address "local" rigidity (lack of internal flex), the transition to "global" rigidity—where the graph has a unique embedding in the plane—remains a subject for future research.
  • 3D Rigidity: Extending these results to 3D is a major challenge. The lack of a simple "Laman-style" combinatorial characterization for 3D rigidity makes this one of the most significant open problems in the field.

Summary updated

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.
BibTeX
@inproceedings{kasiviswanathan2011rigidity,
  author = {Shiva Prasad Kasiviswanathan and Cristopher Moore and Louis Theran},
  title = {{The rigidity transition in random graphs}},
  booktitle = {SODA},
  year = {2011},
  doi = {10.1137/1.9781611973082.94},
}
Figure