Upper tails and independence polynomials in random graphs

DOI10.1016/j.aim.2017.08.003zbMath1370.05099arXiv1507.04074MaRDI QIDQ2404638

Yufei Zhao, Shirshendu Ganguly, Eyal Lubetzky, Bhaswar B. Bhattacharya

Publication date: 19 September 2017

Published in: Advances in Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

large deviations; variational problems; subgraph counts; upper tails; sparse random graphs

Mathematics Subject Classification ID

05C31: Graph polynomials

05C80: Random graphs (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Related Items

Upper Tails for Edge Eigenvalues of Random Graphs, Preferential attachment when stable, A counterexample to the DeMarco‐Kahn upper tail conjecture, On the variational problem for upper tails in sparse random graphs, On the upper tail problem for random hypergraphs, Upper tail for homomorphism counts in constrained sparse random graphs, Large deviations for subcomplex counts and Betti numbers in multiparameter simplicial complexes, Moderate deviations in cycle count, Lower tails via relative entropy, Large deviations in random latin squares, Typical large graphs with given edge and triangle densities, Gaussian-width gradient complexity, reverse log-Sobolev inequalities and nonlinear large deviations, The sample size required in importance sampling, A large deviation principle for the Erdős-Rényi uniform random graph, Anti-concentration for subgraph counts in random graphs, Spectral edge in sparse random graphs: upper and lower tail large deviations, Large deviations for the largest eigenvalue of Gaussian networks with constant average degree, Rare event asymptotics for exploration processes for random graphs, Upper tails via high moments and entropic stability, Large deviation for uniform graphs with given degrees, Localization in random geometric graphs with too many edges, Replica symmetry in upper tails of mean-field hypergraphs, The structure of low-complexity Gibbs measures on product spaces, Nonlinear large deviations: beyond the hypercube, 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, Upper tail bounds for stars, An introduction to large deviations for random graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
• Applications of Stein's method for concentration inequalities
• The large deviation principle for the Erdős-Rényi random graph
• Limits of dense graph sequences
• The roots of the independence polynomial of a clawfree graph
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Matching theory
• A generalization of Hölder's inequality and some probability inequalities
• Best constants in Young's inequality, its converse, and its generalization to more than three functions
• The independence fractal of a graph.
• Gaussian-width gradient complexity, reverse log-Sobolev inequalities and nonlinear large deviations
• Average independence polynomials
• Upper tails for subgraph counts in random graphs
• The deletion method for upper tail estimates
• Nonlinear large deviations
• On the Choice Number of Random Hypergraphs
• An introduction to large deviations for random graphs
• The missing log in large deviations for triangle counts
• Upper tails for triangles
• Tight upper tail bounds for cliques
• On replica symmetry of large deviations in random graphs
• Divide and conquer martingales and the number of triangles in a random graph
• The infamous upper tail
• On the variational problem for upper tails in sparse random graphs