On the Lower Tail Variational Problem for Random Graphs

DOI10.1017/S0963548316000262zbMath1371.05274arXiv1502.00867OpenAlexW1708863771MaRDI QIDQ5366946

Yufei Zhao

Publication date: 10 October 2017

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

lower tail large deviation problemsubgraph counts in a random graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Large deviations (60F10)

Related Items (12)

Upper tails via high moments and entropic stability ⋮ Replica symmetry in upper tails of mean-field hypergraphs ⋮ On the upper tail problem for random hypergraphs ⋮ Upper tail for homomorphism counts in constrained sparse random graphs ⋮ Moderate deviations in cycle count ⋮ Upper Tails for Edge Eigenvalues of Random Graphs ⋮ Lower tails via relative entropy ⋮ Large deviations of subgraph counts for sparse Erdős-Rényi graphs ⋮ Approximating the cumulant generating function of triangles in the Erdös-Rényi random graph ⋮ Moderate deviations of subgraph counts in the Erdős-Rényi random graphs 𝐺(𝑛,𝑚) and 𝐺(𝑛,𝑝) ⋮ A large deviation principle for the Erdős-Rényi uniform random graph ⋮ An introduction to large deviations for random graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The clique density theorem
• Phase transitions in exponential random graphs
• Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
• Asymptotic structure and singularities in constrained directed graphs
• Asymptotic quantization of exponential random graphs
• An approximate version of Sidorenko's conjecture
• The large deviation principle for the Erdős-Rényi random graph
• Limits of dense graph sequences
• Szemerédi's lemma for the analyst
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Reciprocity in directed networks
• Singularities in the entropy of asymptotically large simple graphs
• Asymptotics for sparse exponential random graph models
• A correlation inequality for bipartite graphs
• Moments of two-variable functions and the uniqueness of graph limits
• Asymptotic structure of constrained exponential random graph models
• Multipodal structure and phase transitions in large constrained graphs
• Estimating and understanding exponential random graph models
• Critical phenomena in exponential random graphs
• Large deviations and exact asymptotics for constrained exponential random graphs
• Nonlinear large deviations
• Two approaches to Sidorenko’s conjecture
• The lower tail: Poisson approximation revisited
• Phase transitions in a complex network
• Emergent Structures in Large Networks
• The missing log in large deviations for triangle counts
• Upper tails for triangles
• The number of cliques in graphs of given order and size
• Recent developments in graph Ramsey theory
• On replica symmetry of large deviations in random graphs
• On Sets of Acquaintances and Strangers at any Party
• On the Minimal Density of Triangles in Graphs
• A Disproof of a Conjecture of Erdős in Ramsey Theory
• Poisson approximation for large deviations
• On the asymptotics of constrained exponential random graphs
• On the phase transition curve in a directed exponential random graph model
• The asymptotics of large constrained graphs
• On the variational problem for upper tails in sparse random graphs
• Graph norms and Sidorenko's conjecture

This page was built for publication: On the Lower Tail Variational Problem for Random Graphs