Regular graphs with many triangles are structured

DOI10.37236/10369zbMATH Open1481.05142OpenAlexW4210467702MaRDI QIDQ2073296FDOQ2073296

Authors: Gabor Lippner, Elchanan Mossel, 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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Triangles in regular graphs with density below one half
• The number of large graphs with a positive density of triangles
• The asymptotics of large constrained graphs
• Typical large graphs with given edge and triangle densities
• Triangle-free regular graphs

zbMATH Keywords

large deviationsstructural stability

Mathematics Subject Classification ID

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

Cites Work

• Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
• Nonlinear large deviations
• Phase transitions in a complex network
• On replica symmetry of large deviations in random graphs
• On the variational problem for upper tails in sparse random graphs
• The large deviation principle for the Erdős-Rényi random graph
• Upper tails for subgraph counts in random graphs
• The deletion method for upper tail estimates
• A large deviation result on the number of small subgraphs of a random graph
• The missing log in large deviations for triangle counts
• The infamous upper tail
• Small subgraphs of random regular graphs
• Divide and conquer martingales and the number of triangles in a random graph
• Upper tails for triangles
• The asymptotics of large constrained graphs
• The number of large graphs with a positive density of triangles
• On the large deviations of traces of random matrices
• Bipodal structure in oversaturated random graphs
• The phases of large networks with edge and triangle constraints
• Large deviations of subgraph counts for sparse Erdős-Rényi graphs

Cited In (6)

• Triangles in regular graphs with density below one half
• Large deviation for uniform graphs with given degrees
• Upper tails via high moments and entropic stability
• Typical large graphs with given edge and triangle densities
• The number of large graphs with a positive density of triangles
• On the density of triangles and squares in regular finite and unimodular random graphs

This page was built for publication: Regular graphs with many triangles are structured

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2073296)