On rigidity, orientability and cores of random graphs with sliders

Julien Barré, Florent Krząkała, Dieter MitschearXiv 2014 · DOI · arXiv

TL;DR

This paper provides a rigorous mathematical framework for understanding "rigidity percolation" in networks where nodes have varying degrees of freedom. By introducing novel concepts like 1.5-orientability and the 2.5-core, the authors pinpoint the exact moment a giant rigid structure emerges in random graphs and reveal a "tricritical" point where the nature of this transition shifts from smooth to abrupt.

What Problem Does This Paper Address?

Imagine a set of points in a 2D plane connected by rigid bars. If you have enough bars, the whole structure becomes a single "rigid" block that can only move as a solid body. This is a classic problem in combinatorial rigidity.

Standard models usually assume every point is "free" (2 degrees of freedom). However, real-world systems like proteins or molecular glasses often have mixed constraints. This paper explores a hybrid model: some points move freely, while others are "sliders" constrained to move only along fixed lines (1 degree of freedom).

The central question is: At what density of bars ($c$) does a "giant" rigid component—one containing a positive fraction of all points—suddenly appear? Furthermore, how does the proportion of free points ($q$) vs. sliders ($1-q$) change the "flavor" of this transition?

Methods

The authors bridge the gap between physical rigidity and pure graph theory. They rely on the fact that for "generic" placements of points, rigidity depends only on the graph's topology, not the specific coordinates.

Key innovations include:

  • 1.5-Orientability: A new graph-theoretic property where edges are directed such that "slider" nodes have an in-degree of at most 1, and "free" nodes have an in-degree of at most 2. This effectively "counts" the degrees of freedom available to be "consumed" by rigid bars.
  • The 2.5-Core: A generalization of the standard $k$-core. It is the largest subgraph where sliders have a minimum degree of 2 and free nodes have a minimum degree of 3.
  • Probabilistic Analysis: The authors use the Erdős-Rényi random graph model $G(n, c/n)$ and apply generating functions and differential equations (specifically the method of Janson and Luczak) to track how these cores emerge as the edge density $c$ increases.

Datasets

As a theoretical mathematics and physics paper, it does not use empirical datasets. Instead, it performs analytical derivations and proofs based on the Erdős-Rényi random graph model, which serves as the standard benchmark for studying phase transitions in network science.

Key Insights and Ideas

  • The Tricritical Point ($q = 1/2$): The most striking finding is that the phase transition changes qualitatively based on the mix of nodes.
  • If more than half the nodes are sliders ($q \leq 1/2$), the giant rigid component grows continuously from zero size.
  • If more than half are free points ($q > 1/2$), the transition is discontinuous—the giant component "snaps" into existence at a significant size.
  • Mathematical Interpolation: The "1.5" and "2.5" terminology represents a formal interpolation between standard connectivity (which relates to 1-orientability and the 2-core) and 2D rigidity (which relates to 2-orientability and the 3-core).
  • Matroid Structure: The authors prove that the collection of "minimally rigid" graphs with sliders forms a matroid. This is a deep structural result that implies a unique decomposition of any graph into its rigid components.

Key Results

  • Threshold Formula: The paper derives a precise analytical expression for the threshold $c^*(q)$ at which the giant rigid component appears.
  • Generalization: The results recover known values for the extremes:
  • When $q=1$ (all free points), the threshold is $c \approx 3.588$, matching previous studies of 2D rigidity.
  • When $q=0$ (all sliders), the threshold is $c=1$, matching the standard threshold for the emergence of a giant connected component.
  • Conjecture Proof: The authors formally prove a previous conjecture regarding the size and emergence of the "3+2-core" (a specific type of extended core used in physics).

Limitations and Future Work

  • Erdős-Rényi Limitation: The analysis assumes edges are placed completely at random. Real-world networks (like the amino acid networks in proteins) often have spatial constraints or "small-world" properties that might alter the threshold.
  • Dimensionality: The study is strictly 2D. Extending these "fractional core" concepts to 3D rigidity is a major open challenge, as the underlying combinatorial characterization of 3D rigidity (the 3D version of Laman’s Theorem) is famously unsolved.
  • Generic Assumption: The results hold for "generic" frameworks. Singular geometries (e.g., three points on a perfect line) could behave differently, though these are statistically rare in random systems.

Summary updated

Abstract

Suppose that you add rigid bars between points in the plane, and suppose that a constant fraction $q$ of the points moves freely in the whole plane; the remaining fraction is constrained to move on fixed lines called sliders. When does a giant rigid cluster emerge? Under a genericity condition, the answer only depends on the graph formed by the points (vertices) and the bars (edges). We find for the random graph $G \in \mathcal{G}(n,c/n)$ the threshold value of $c$ for the appearance of a linear-sized rigid component as a function of $q$, generalizing results of Kasiviswanathan et al. We show that this appearance of a giant component undergoes a continuous transition for $q \leq 1/2$ and a discontinuous transition for $q > 1/2$. In our proofs, we introduce a generalized notion of orientability interpolating between 1- and 2-orientability, of cores interpolating between 2-core and 3-core, and of extended cores interpolating between 2+1-core and 3+2-core; we find the precise expressions for the respective thresholds and the sizes of the different cores above the threshold. In particular, this proves a conjecture of Kasiviswanathan et al. about the size of the 3+2-core. We also derive some structural properties of rigidity with sliders (matroid and decomposition into components) which can be of independent interest.
BibTeX
@misc{barre2014rigidity,
  author = {Julien Barré and Florent Krząkała and Dieter Mitsche},
  title = {{On rigidity, orientability and cores of random graphs with sliders}},
  year = {2014},
  eprint = {1412.1004},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1412.1004},
}
Figure