A first order phase transition for lower tails in sparse random graphs
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 \gg n^{-1/m_2(H)}$, we transfer these results to the conditioned random graph,…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.27457
curl -X POST /api/v1/records/arxiv/2610.27457/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.27457/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'