Upper tails and independence polynomials in random graphs

By Bhaswar B. Bhattacharya, S. Ganguly, Eyal Lubetzky, Yufei Zhao. 2015

62 citations recorded by the source corpus.

Abstract The upper tail problem in the Erdős–Renyi random graph G ∼ G n , p asks to estimate the probability that the number of copies of a graph H in G exceeds its expectation by a factor 1 + δ . Chatterjee and Dembo showed that in the sparse regime of p → 0 as n → ∞ with p ≥ n − α for an explicit α = α H > 0 , this problem reduces to a natural variational problem on weighted graphs, which was thereafter asymptotically solved by two of the authors in the case where H is a clique. Here we extend the latter work to any fixed graph H and determine a function c H ( δ ) such that, for p as above and any fixed δ > 0 , the upper tail probability is exp ⁡ [ − ( c H ( δ ) + o ( 1 ) ) n 2 p Δ log ⁡ ( 1 / p ) ] , where Δ is the maximum degree of H. As it turns out, the leading order constant in the large deviation rate function, c H ( δ ) , is governed by the independence polynomial of H, defined as P H ( x ) = ∑ i H ( k ) x k where i H ( k ) is the number of independent sets of size k in H. For instance, if H is a regular graph on m vertices, then c H ( δ ) is the minimum between 1 2 δ 2 / m and the unique positive solution of P H ( x ) = 1 + δ .

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/4af552cc90c7b2d139b28075d58c4251604e153a

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Discrete Mathematics and Combinatorics

In Geometry and Topology

Citations in the corpus

Large deviations of subgraph counts for sparse Erdős–Rényi graphs (2018, background): “∞ at the expense of increasing the power of the logarithmic corrections in the lower bounds on p by O(C) (as can be seen from (3.9), taking W(N) to grow poly-logarithmically). The following result of [BGLZ17] (extending the earlier work [LZ17] for the case of cliques), solves the upper tail variatio”
Gaussian-width gradient complexity, reverse log-Sobolev inequalities and nonlinear large deviations (2016, background): “…T , it turns out that when maximizing over product measures ν , the right hand side becomes a tractable quantity which can be calculated almost precisely, as was done in Lubetzky and Zhao [2014] for the case of triangles, and later in Bhattacharya et al. [2017] for general subgraph counts.”
Upper tails via high moments and entropic stability (2019, methodology): “The following lemma formalises this statement; its proof is similar to an argument of Lubetzky and Zhao [51].”
An introduction to large deviations for random graphs (2016, background): “…years ago, large deviations theory did not have the tools to answer such basic questions about nonlinear functions of independent random variables, although a number of powerful concentration inequalities were available for computing upper and lower bounds on tail probabilities [35, 37, 48, 50].”
The sample size required in importance sampling (2015, background): “Recently, a variety of exponential random graph models have been explicitly ‘solved’ (see Chatterjee and Diaconis [16], Kenyon, Radin, Ren and Sadun [35], Kenyon and Yin [36] and Bhattacharya, Ganguly, Lubetzky and Zhao [6]).”