{
  "id": "2202.09917",
  "version": "v2",
  "published": "2022-02-20T22:07:14.000Z",
  "updated": "2022-09-13T12:47:34.000Z",
  "title": "Sharp threshold for rigidity of random graphs",
  "authors": [
    "Alan Lew",
    "Eran Nevo",
    "Yuval Peled",
    "Orit E. Raz"
  ],
  "categories": [
    "math.CO",
    "math.PR"
  ],
  "abstract": "We consider the Erd\\H{o}s-R\\'enyi evolution of random graphs, where a new uniformly distributed edge is added to the graph in every step. For every fixed $d\\ge 1$, we show that with high probability, the graph becomes rigid in $\\mathbb R^d$ at the very moment its minimum degree becomes $d$, and it becomes globally rigid in $\\mathbb R^d$ at the very moment its minimum degree becomes $d+1$.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2022-09-13T12:47:34.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C80",
      "52C25"
    ],
    "keywords": [
      "random graphs",
      "sharp threshold",
      "minimum degree",
      "high probability",
      "uniformly distributed edge"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}