{
  "id": "2303.09198",
  "version": "v1",
  "published": "2023-03-16T10:15:11.000Z",
  "updated": "2023-03-16T10:15:11.000Z",
  "title": "Large deviations for triangles in scale-free random graphs",
  "authors": [
    "Clara Stegehuis",
    "Bert Zwart"
  ],
  "categories": [
    "math.PR"
  ],
  "abstract": "We provide large deviations estimates for the upper tail of the number of triangles in scale-free inhomogeneous random graphs where the degrees have power law tails with index $-\\alpha, \\alpha \\in (1,2)$. We show that upper tail probabilities for triangles undergo a phase transition. For $\\alpha<4/3$, the upper tail is caused by many vertices of degree of order $n$, and this probability is semi-exponential. In this regime, additional triangles consist of two hubs. For $\\alpha>4/3$ on the other hand, the upper tail is caused by one hub of a specific degree, and this probability decays polynomially in $n$, leading to additional triangles with one hub. In the intermediate case $\\alpha=4/3$, we show polynomial decay of the tail probability caused by multiple but finitely many hubs. In this case, the additional triangles contain either a single hub or two hubs. Our proofs are partly based on various concentration inequalities. In particular, we tailor concentration bounds for empirical processes to make them well-suited for analyzing heavy-tailed phenomena in nonlinear settings.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-03-16T10:15:11.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "scale-free random graphs",
      "upper tail",
      "tail probability",
      "scale-free inhomogeneous random graphs",
      "additional triangles consist"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}