Structure of lower tails in sparse random graphs
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915092758528000 |
|---|---|
| author | Chin, Byron |
| author_facet | Chin, Byron |
| contents | We study the typical structure of a sparse Erdős--Rényi random graph conditioned on the lower tail subgraph count event. We show that in certain regimes, a typical graph sampled from the conditional distribution resembles the entropy minimizer of the mean field approximation in the sense of both subgraph counts and cut norm. The main ingredients are an adaptation of an entropy increment scheme of Kozma and Samotij, and a new stability for the solution of the associated entropy variational problem.
The proof can be interpreted as a structural application of the new probabilistic hypergraph container lemma for sparser than average sets, and suggests a more general framework for establishing such typical behavior statements. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_12673 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Structure of lower tails in sparse random graphs Chin, Byron Combinatorics Probability We study the typical structure of a sparse Erdős--Rényi random graph conditioned on the lower tail subgraph count event. We show that in certain regimes, a typical graph sampled from the conditional distribution resembles the entropy minimizer of the mean field approximation in the sense of both subgraph counts and cut norm. The main ingredients are an adaptation of an entropy increment scheme of Kozma and Samotij, and a new stability for the solution of the associated entropy variational problem. The proof can be interpreted as a structural application of the new probabilistic hypergraph container lemma for sparser than average sets, and suggests a more general framework for establishing such typical behavior statements. |
| title | Structure of lower tails in sparse random graphs |
| topic | Combinatorics Probability |
| url | https://arxiv.org/abs/2312.12673 |