On the variational problem for upper tails in sparse random graphs

DOI10.1002/RSA.20658MaRDI QIDQ5739097zbMATH OpenOpenAlexFDO

Authors Eyal Lubetzky, Yufei Zhao

Publication date 2 June 2017

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1402.6011

zbMATH Keywords

large deviationssparse random graphsupper tails of subgraph counts

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Density (toughness, etc.) (05C42)

Abstract: What is the probability that the number of triangles in $mathcal{G}_{n,p}$, the ErdH{o}s-R'enyi random graph with edge density $p$, is at least twice its mean? Writing it as $exp[-r(n,p)]$, already the order of the rate function $r(n,p)$ was a longstanding open problem when $p=o(1)$, finally settled in 2012 by Chatterjee and by DeMarco and Kahn, who independently showed that $r(n,p)asymp{n}^2{p}^{2}log(1/p)$ for $pgtrsimfraclognn$; the exact asymptotics of $r(n,p)$ remained unknown. The following variational problem can be related to this large deviation question at $pgtrsimfraclognn$: for $delta>0$ fixed, what is the minimum asymptotic $p$-relative entropy of a weighted graph on $n$ vertices with triangle density at least $(1+delta)p^3$? A beautiful large deviation framework of Chatterjee and Varadhan (2011) reduces upper tails for triangles to a limiting version of this problem for fixed $p$. A very recent breakthrough of Chatterjee and Dembo extended its validity to $n^{-alpha}llpll1$ for an explicit $alpha>0$, and plausibly it holds in all of the above sparse regime. In this note we show that the solution to the variational problem is $minfrac12delt{a}^{2/3},,,frac13delta$ when $n^{-1/2}llpll1$ vs. $frac12delt{a}^{2/3}$ when $n^{-1}llpll{n}^{-1/2}$ (the transition between these regimes is expressed in the count of triangles minus an edge in the minimizer). From the results of Chatterjee and Dembo, this shows for instance that the probability that $mathcal{G}_{n,p}$ for $n^{-alpha}leqpll1$ has twice as many triangles as its expectation is $exp[-r(n,p)]$ where $r(n,p)simfrac13n^2{p}^{2}log(1/p)$. Our results further extend to $k$-cliques for any fixed $k$, as well as give the order of the upper tail rate function for an arbitrary fixed subgraph when $pgeq{n}^{-alpha}$.

Recommendations

• Upper tails and independence polynomials in random graphs
• On the lower tail variational problem for random graphs
• Upper tails for triangles
• Large deviations of subgraph counts for sparse Erdős-Rényi graphs
• On the upper tail problem for random hypergraphs

Cites work

• A generalization of Hölder's inequality and some probability inequalities
• A large deviation result on the number of small subgraphs of a random graph
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Divide and conquer martingales and the number of triangles in a random graph
• Large networks and graph limits
• Limits of dense graph sequences
• On replica symmetry of large deviations in random graphs
• Quick approximation to matrices and applications
• Szemerédi's lemma for the analyst
• The deletion method for upper tail estimates
• The infamous upper tail
• The large deviation principle for the Erdős-Rényi random graph
• The missing log in large deviations for triangle counts
• Tight upper tail bounds for cliques
• Upper tails and independence polynomials in random graphs
• Upper tails for subgraph counts in random graphs
• Upper tails for triangles

Cited in

(50)

• Moderate deviations of triangle counts in the Erdős-Rényi random graph G (n, m): the lower tail
• Upper tails for edge eigenvalues of random graphs
• Large deviations for the largest eigenvalue of Gaussian networks with constant average degree
• Large deviation for uniform graphs with given degrees
• Upper tails via high moments and entropic stability
• Localization in random geometric graphs with too many edges
• On the lower tail variational problem for random graphs
• Large deviations of the empirical spectral measure of supercritical sparse Wigner matrices
• On the upper tail problem for random hypergraphs
• Moderate deviations of triangle counts in sparse Erdős-Rényi random graphs G(n, m) and G(n, p)
• A large deviation principle for the Erdős-Rényi uniform random graph
• Large deviation principles for graphon sampling
• Anti-concentration for subgraph counts in random graphs
• Spectral large deviations of sparse random matrices
• Moderate deviations of triangle counts -- the lower tail (extended abstract)
• Gaussian-width gradient complexity, reverse log-Sobolev inequalities and nonlinear large deviations
• Large deviations of subgraph counts for sparse Erdős-Rényi graphs
• Nonlinear large deviation bounds with applications to Wigner matrices and sparse Erdős-Rényi graphs
• Typical structure of sparse exponential random graph models
• Upper tails for triangles
• Optimal graphons in the edge-2star model
• Moderate deviations of subgraph counts in the Erdős-Rényi random graphs \(G(n,m)\) and \(G(n,p)\)
• Upper tail behavior of the number of triangles in random graphs with constant average degree
• Upper tail for homomorphism counts in constrained sparse random graphs
• A detailed investigation into near degenerate exponential random graphs
• Ground states for exponential random graphs
• Nonlinear large deviations: beyond the hypercube
• The structure of low-complexity Gibbs measures on product spaces
• Spectral edge in sparse random graphs: upper and lower tail large deviations
• Upper tails and independence polynomials in random graphs
• Decomposition of mean-field Gibbs distributions into product measures
• Upper tail of the spectral radius of sparse Erdös-Rényi graphs
• Sub-Gaussian tails for the number of triangles in G( n, p)
• Upper Tail Large Deviations of Regular Subgraph Counts in Erdős‐Rényi Graphs in the Full Localized Regime
• A counterexample to the DeMarco-Kahn upper tail conjecture
• Large deviations for subcomplex counts and Betti numbers in multiparameter simplicial complexes
• Moderate deviations in cycle count
• Replica symmetry in upper tails of mean-field hypergraphs
• Upper tail bounds for stars
• Universality in prelimiting tail behavior for regular subgraph counts in the Poisson regime
• Rare event asymptotics for exploration processes for random graphs
• Concentration inequalities for non-Lipschitz functions with bounded derivatives of higher order
• Phase transitions in edge-weighted exponential random graphs: near-degeneracy and universality
• Regular graphs with many triangles are structured
• Modified log-Sobolev inequalities, Beckner inequalities and moment estimates
• Lower tails via relative entropy
• Upper tail bounds for cycles
• Preferential attachment when stable
• Asymptotic structure of graphs with the minimum number of triangles
• The upper tail problem for induced 4‐cycles in sparse random graphs

This page was built for publication: On the variational problem for upper tails in sparse random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5739097)