pipette
ENEnglish

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

Byron Chin

Preprint

En palabras de los autores

We study the graphon variational problem that governs lower tail large deviations of the number of copies of a fixed nonbipartite graph in a sparse Erd\H{o}s--R\'enyi 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 , 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.

Resultado principalEl resumen no menciona limitaciones.

Apareció: miércoles, 21 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 20 pages