Upper tails via high moments and entropic stability

DOI10.1215/00127094-2021-0067zbMath1500.60002arXiv1904.08212OpenAlexW2939354510MaRDI QIDQ2165741

Frank Mousset, Wojciech Samotij, Matan Harel

Publication date: 22 August 2022

Published in: Duke Mathematical Journal (Search for Journal in Brave)

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

zbMATH Keywords

random graphsarithmetic progressionsconcentration inequalitiesupper tailsnonlinear large deviations

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Large deviations (60F10)

Related Items

Localization in random geometric graphs with too many edges, Substructures in Latin squares, Upper tail of the spectral radius of sparse Erdös-Rényi graphs, On the upper tail problem for random hypergraphs, Upper Tails for Edge Eigenvalues of Random Graphs, Lower tails via relative entropy, Large deviations in random latin squares, Deviation probabilities for arithmetic progressions and irregular discrete structures, Large deviations of subgraph counts for sparse Erdős-Rényi graphs, Typical large graphs with given edge and triangle densities, Local limit theorems for subgraph counts, Large deviations for the largest eigenvalue of Gaussian networks with constant average degree

Cites Work

• On the upper tail of counts of strictly balanced subgraphs
• The large deviation principle for the Erdős-Rényi random graph
• Shadows and intersections: Stability and new proofs
• When are small subgraphs of a random graph normally distributed?
• Some intersection theorems for ordered sets and graphs
• On the number of subgraphs of prescribed type of graphs with a given number of edges
• A central limit theorem for decomposable random variables with applications to random graphs
• On the number of copies of one hypergraph in another
• Gaussian-width gradient complexity, reverse log-Sobolev inequalities and nonlinear large deviations
• Upper tails for arithmetic progressions in random subsets
• Decomposition of mean-field Gibbs distributions into product measures
• Counting cycles and finite dimensional \(L^{p}\) norms
• Upper tails for subgraph counts in random graphs
• Concentration of measure and isoperimetric inequalities in product spaces
• A large deviation principle for the Erdős-Rényi uniform random graph
• A transportation approach to the mean-field approximation
• Regular graphs with many triangles are structured
• Localization in random geometric graphs with too many edges
• Replica symmetry in upper tails of mean-field hypergraphs
• On the probability of nonexistence in binomial subsets
• The structure of low-complexity Gibbs measures on product spaces
• 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
• On the missing log in upper tail estimates
• Bivariate fluctuations for the number of arithmetic progressions in random sets
• Upper tail bounds for stars
• Large deviations for random graphs. École d'Été de Probabilités de Saint-Flour XLV -- 2015
• Upper tails and independence polynomials in random graphs
• Upper tails for counting objects in randomly induced subhypergraphs and rooted random graphs
• Estimating and understanding exponential random graph models
• The deletion method for upper tail estimates
• Nonlinear large deviations
• The typical structure of sparse $K_{r+1}$-free graphs
• The lower tail: Poisson approximation revisited
• Concentration Inequalities
• Graph Theory
• The missing log in large deviations for triangle counts
• Tight upper tail bounds for cliques
• On replica symmetry of large deviations in random graphs
• Moderate deviations of subgraph counts in the Erdős-Rényi random graphs 𝐺(𝑛,𝑚) and 𝐺(𝑛,𝑝)
• Threshold functions for small subgraphs
• Poisson approximation for large deviations
• Divide and conquer martingales and the number of triangles in a random graph
• On the concentration of multivariate polynomials with small expectation
• Concentration of non‐Lipschitz functions and applications
• The infamous upper tail
• Upper Tail Large Deviations for Arithmetic Progressions in a Random Set
• A counterexample to the DeMarco‐Kahn upper tail conjecture
• Probability Inequalities for Sums of Bounded Random Variables
• On the Lower Tail Variational Problem for Random Graphs
• On the maximal number of 3-term arithmetic progressions in subsets of ℤ/p ℤ
• On the variational problem for upper tails in sparse random graphs
• Gaussian Width Bounds with Applications to Arithmetic Progressions in Random Settings
• Concentration of multivariate polynomials and its applications
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item