Skip to content
DraconiticResearch
Search Sources API
197,761 studies31 sourcesUpdated 38 min ago
PreprintarXiv licencearXiv

A first order phase transition for lower tails in sparse random graphs

  • Byron Chin
Open at sourcePDFDOICite

Abstract

We study the graphon variational problem that governs lower tail large deviations of the number of copies of a fixed nonbipartite graph H in a sparse Erdős--Rényi random graph. Our main new insight is that any non-constant minimizer of the variational problem exhibits a discontinuous jump away from the constant graphon. We deduce that the replica-symmetric and symmetry-breaking regimes are separated by a single critical parameter and that the phase transition is first order. In the supercritical regime p ≫ n−1/m2(H), we transfer these results to the conditioned random graph, showing that the edge density is a discontinuous order parameter and that the conditioned graph concentrates in cut distance near the full minimizer set.

Related

  1. First-Order Laws for Random Geometric Graphs on the Torus
    Simi Haber, Mostafa Mirabi, Saharon Shelah
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsLogic & foundationsarXiv
  2. Optimal path decompositions of sparse random graphs
    Jifu Lin, Heng Yang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Coloring sparse random Cayley graphs
    Nathan Tung
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsProbabilityarXiv
  4. The lower tail of triangle counts in sparse random graphs
    Dong Huang, Shuangping Li
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsProbabilityarXiv
  5. Local Convergence of Triadic Closures of Sparse Random Graphs
    Himasish Talukdar
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsMathematical physicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{chin2026first,
  title = {{A first order phase transition for lower tails in sparse random graphs}},
  author = {Byron Chin},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.27457},
  eprint = {2610.27457},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.27457},
}
RIS
TY  - UNPB
TI  - A first order phase transition for lower tails in sparse random graphs
AU  - Byron Chin
PY  - 2026
DA  - 2026/10/20
PB  - arXiv
DO  - 10.48550/arxiv.2610.27457
UR  - https://arxiv.org/abs/2610.27457
AB  - We study the graphon variational problem that governs lower tail large deviations of the number of copies of a fixed nonbipartite graph H in a sparse Erdős--Rényi random graph. Our main new insight is that any non-constant minimizer of the variational problem exhibits a discontinuous jump away from the constant graphon. We deduce that the replica-symmetric and symmetry-breaking regimes are separated by a single critical parameter and that the phase transition is first order. In the supercritical regime p ≫ n^−1/m_2(H), we transfer these results to the conditioned random graph, showing that the edge density is a discontinuous order parameter and that the conditioned graph concentrates in cut distance near the full minimizer set.
ER  -