On rigidity, orientability and cores of random graphs with sliders

Description

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 ∈ 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 [7]. We show that this appearance of a giant component undergoes a continuous transition for q ≤ 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 [7] 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.

Additional details