Regular graphs with many triangles are structured

DOI10.37236/10369zbMath1481.05142OpenAlexW4210467702MaRDI QIDQ2073296

Elchanan Mossel, Gabor Lippner, Pim Van der Hoorn

Publication date: 1 February 2022

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.37236/10369

zbMATH Keywords

structural stabilitylarge deviations

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Enumeration in graph theory (05C30) Combinatorial probability (60C05) Structural characterization of families of graphs (05C75)

Related Items

Upper tails via high moments and entropic stability, Large deviation for uniform graphs with given degrees

Cites Work

• The large deviation principle for the Erdős-Rényi random graph
• Small subgraphs of random regular graphs
• Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
• On the large deviations of traces of random matrices
• The number of large graphs with a positive density of triangles
• Upper tails for subgraph counts in random graphs
• Large deviations of subgraph counts for sparse Erdős-Rényi graphs
• The deletion method for upper tail estimates
• Nonlinear large deviations
• On the Choice Number of Random Hypergraphs
• Phase transitions in a complex network
• The missing log in large deviations for triangle counts
• Upper tails for triangles
• 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
• The phases of large networks with edge and triangle constraints
• Bipodal Structure in Oversaturated Random Graphs
• The asymptotics of large constrained graphs
• On the variational problem for upper tails in sparse random graphs