Regular graphs with many triangles are structured

DOI10.37236/10369MaRDI QIDQ2073296zbMATH OpenOpenAlexFDO

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)

Copyright license Creative Commons Attribution 4.0 International

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

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

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)

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

Cites work

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

Cited in

(6)

• The number of large graphs with a positive density of triangles
• Triangles in regular graphs with density below one half
• Typical large graphs with given edge and triangle densities
• Large deviation for uniform graphs with given degrees
• Upper tails via high moments and entropic stability
• 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)