On replica symmetry of large deviations in random graphs

DOI10.1002/rsa.20536zbMath1348.05195arXiv1210.7013OpenAlexW3111617893MaRDI QIDQ3192375

Eyal Lubetzky, Yufei Zhao

Publication date: 12 October 2015

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

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

zbMATH Keywords

random graphslarge deviationssymmetry breakingreplica symmetry

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Distance in graphs (05C12)

Related Items (46)

Reciprocity in directed networks ⋮ Nonlinear large deviations ⋮ Exponential random graphs behave like mixtures of stochastic block models ⋮ Interview with Yufei Zhao ⋮ A detailed investigation into near degenerate exponential random graphs ⋮ Cut norm discontinuity of triangular truncation of graphons ⋮ Upper tails via high moments and entropic stability ⋮ Large deviation for uniform graphs with given degrees ⋮ Upper tails and independence polynomials in random graphs ⋮ Extremal Regular Graphs: Independent Sets and Graph Homomorphisms ⋮ Multipodal structure and phase transitions in large constrained graphs ⋮ Upper tails for arithmetic progressions in random subsets ⋮ Replica symmetry in upper tails of mean-field hypergraphs ⋮ Upper tail of the spectral radius of sparse Erdös-Rényi graphs ⋮ 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 ⋮ The phases of large networks with edge and triangle constraints ⋮ The upper tail problem for induced 4‐cycles in sparse random graphs ⋮ Upper Tail Large Deviations of Regular Subgraph Counts in Erdős‐Rényi Graphs in the Full Localized Regime ⋮ Large deviations of subgraph counts for sparse Erdős-Rényi graphs ⋮ A sample-path large deviation principle for dynamic Erdős-Rényi random graphs ⋮ Rigidity of proper colorings of \(\mathbb{Z}^d \) ⋮ Breaking of ensemble equivalence for dense random graphs under a single constraint ⋮ Asymptotic Structure of Graphs with the Minimum Number of Triangles ⋮ On the Lower Tail Variational Problem for Random Graphs ⋮ Estimating and understanding exponential random graph models ⋮ Approximating the cumulant generating function of triangles in the Erdös-Rényi random graph ⋮ Independent sets in graphs ⋮ A large deviation principle for the Erdős-Rényi uniform random graph ⋮ Ensemble equivalence for dense graphs ⋮ Phase transitions in edge-weighted exponential random graphs: near-degeneracy and universality ⋮ On the variational problem for upper tails in sparse random graphs ⋮ Spectral edge in sparse random graphs: upper and lower tail large deviations ⋮ An introduction to large deviations for random graphs ⋮ Upper tail bounds for stars ⋮ An 𝐿^{𝑝} theory of sparse graph convergence I: Limits, sparse random graph models, and power law distributions ⋮ The number of independent sets in an irregular graph ⋮ Regular graphs with many triangles are structured ⋮ A reverse Sidorenko inequality ⋮ Matrix estimation by universal singular value thresholding ⋮ Large deviations for the largest eigenvalue of Gaussian networks with constant average degree ⋮ Large deviation principle for the maximal eigenvalue of inhomogeneous Erdős-Rényi random graphs ⋮ Ground states for exponential random graphs

Cites Work

• Phase transitions in exponential random graphs
• A measure-theoretic approach to the theory of dense hypergraphs
• Applications of Stein's method for concentration inequalities
• An approximate version of Sidorenko's conjecture
• The large deviation principle for the Erdős-Rényi random graph
• Mixing time of exponential random graphs
• Limits of dense graph sequences
• Szemerédi's lemma for the analyst
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Large deviations techniques and applications.
• Quick approximation to matrices and applications
• Independent sets in regular graphs and sum-free subsets of finite groups
• A generalization of Hölder's inequality and some probability inequalities
• Upper tails for subgraph counts in random graphs
• A correlation inequality for bipartite graphs
• Estimating and understanding exponential random graph models
• Extremal results in sparse pseudorandom graphs
• Hypergraph regularity and the multidimensional Szemerédi theorem
• The deletion method for upper tail estimates
• On the Choice Number of Random Hypergraphs
• An Entropy Approach to the Hard-Core Model on Bipartite Graphs
• The missing log in large deviations for triangle counts
• Upper tails for triangles
• The Bipartite Swapping Trick on Graph Homomorphisms
• Tight upper tail bounds for cliques
• The Number of Independent Sets in a Regular Graph
• Hypergraphs, Entropy, and Inequalities
• On a General Class of Models for Interaction
• Regularity lemmas for hypergraphs and quasi-randomness
• Szemerédi’s Regularity Lemma for Sparse Graphs
• Divide and conquer martingales and the number of triangles in a random graph
• The infamous upper tail
• Regularity Lemma for k-uniform hypergraphs
• Maximizing H‐Colorings of a Regular Graph
• Phase transition in the random triangle model
• The counting lemma for regular k‐uniform hypergraphs
• Graph norms and Sidorenko's conjecture

This page was built for publication: On replica symmetry of large deviations in random graphs