{
  "id": "1412.1004",
  "version": "v1",
  "published": "2014-12-02T18:21:09.000Z",
  "updated": "2014-12-02T18:21:09.000Z",
  "title": "On rigidity, orientability and cores of random graphs with sliders",
  "authors": [
    "Julien Barré",
    "Marc Lelarge",
    "Dieter Mitsche"
  ],
  "comment": "29 pages, 1 figure",
  "categories": [
    "math.CO",
    "math.PR"
  ],
  "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-12-02T18:21:09.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "random graph",
      "orientability",
      "giant rigid cluster emerge",
      "giant component undergoes",
      "add rigid bars"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 29,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1412.1004B"
    }
  }
}