On the lower tail variational problem for random graphs
arXiv:1502.00867 · doi:10.1017/S0963548316000262
Abstract
We study the lower tail large deviation problem for subgraph counts in a random graph. Let denote the number of copies of in an Erdős-Rényi random graph . We are interested in estimating the lower tail probability for fixed . Thanks to the results of Chatterjee, Dembo, and Varadhan, this large deviation problem has been reduced to a natural variational problem over graphons, at least for (and conjecturally for a larger range of ). We study this variational problem and provide a partial characterization of the so-called "replica symmetric" phase. Informally, our main result says that for every , and for some , as slowly, the main contribution to the lower tail probability comes from Erdős-Rényi random graphs with a uniformly tilted edge density. On the other hand, this is false for non-bipartite and close to 1.
arXiv comment15 pages, 5 figures, 1 table
References in corpus (21)
- Estimating and understanding exponential random graph models
- The Clique Density Theorem
- Phase transitions in a complex network
- Applications of Stein's method for concentration inequalities
- On replica symmetry of large deviations in random graphs
- The Asymptotics of Large Constrained Graphs
- Upper tails for triangles
- On the variational problem for upper tails in sparse random graphs
- An information theoretic approach to Sidorenko's conjecture
- Phase transitions in exponential random graphs
- On the logarithimic calculus and Sidorenko's conjecture
- Singularities in the entropy of asymptotically large simple graphs
- The lower tail: Poisson approximation revisited
- Critical phenomena in exponential random graphs
- On the phase transition curve in a directed exponential random graph model
- Asymptotic structure and singularities in constrained directed graphs
- Asymptotic quantization of exponential random graphs
- Asymptotics for Sparse Exponential Random Graph Models
- Reciprocity in directed networks
- Asymptotic Structure of Constrained Exponential Random Graph Models
- Large deviations and exact asymptotics for constrained exponential random graphs