Université Nice Sophia Antipolis
Title
On rigidity, orientability and cores of random graphs with sliders
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 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 a random graph 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, Moore and Theran. We show that this appearance of a giant component undergoes a continuous transition for q smaller than or equal to 1/2 and a discontinuous transition for q bigger than 1/2. In doing that, 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, Moore and Theran about the size of the (3 + 2)-core.
This is joint work with Julien Barré and Marc Lelarge.
