Université Nice Sophia Antipolis



On rigidity, orientability and cores of random graphs with sliders


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.


The Catalan Mathematical Society invites participants to this first congress of a biannual series focusing on current research topics across several areas of Mathematics.

Plenary talks and thematic sessions have been selected by the Scientific Committee of the SCM. Special thanks are due to the organisers of the thematic sessions and to the local mathematical community as a whole for their support to this congress.



Societat Catalana de Matemàtiques
Institut d'Estudis Catalans
Carrer del Carme, 47
08001 Barcelona

Phone: +34 933 248 583

Download a poster (high res)

Download a poster (low res)