Upper tail large deviations of regular subgraph counts in Erd\H{o}s-R\'{e}nyi graphs in the full localized regime
| Autor: | Basak, Anirban, Basu, Riddhipratim |
|---|---|
| Rok vydání: | 2019 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | For a $\Delta$-regular connected graph ${\sf H}$ the problem of determining the upper tail large deviation for the number of copies of ${\sf H}$ in $\mathbb{G}(n,p)$, an Erd\H{o}s-R\'{e}nyi graph on $n$ vertices with edge probability $p$, has generated significant interests. For $p\ll 1$ and $np^{\Delta/2} \gg (\log n)^{1/(v_{\sf H}-2)}$, where $v_{\sf H}$ is the number of vertices in ${\sf H}$, the upper tail large deviation event is believed to occur due to the presence of localized structures. In this regime the large deviation event that the number of copies of ${\sf H}$ in $\mathbb{G}(n,p)$ exceeds its expectation by a constant factor is predicted to hold at a speed $n^2 p^{\Delta} \log (1/p)$ and the rate function is conjectured to be given by the solution of a mean-field variational problem. After a series of developments in recent years, covering progressively broader ranges of $p$, the upper tail large deviations for cliques of fixed size was proved by Harel, Mousset, and Samotij \cite{hms} in the entire localized regime. This paper establishes the conjecture for all connected regular graphs in the whole localized regime. Comment: This version extends the main result of V1 to all connected regular graphs. The title, the main result, and its proof are changed accordingly. 54 pages, 3 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|