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

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

Review text

Summary: We compute the leading asymptotics of the logarithm of the number of \(d\)-regular graphs having at least a fixed positive fraction \(c\) of the maximum possible number of triangles, and provide a strong structural description of almost all such graphs. When \(d\) is constant, we show that such graphs typically consist of many disjoint \((d+1)\)-cliques and an almost triangle-free part. When \(d\) is allowed to grow with \(n\), we show that such graphs typically consist of very dense sets of size \(d+o(d)\) together with an almost triangle-free part. This confirms a conjecture of \textit{P. Collet} and \textit{J. P. Eckmann} [J. Stat. Phys. 109, No. 5--6, 923--943 (2002; Zbl 1011.05028)] and considerably strengthens their observation that the triangles cannot be totally scattered in typical instances of regular graphs with many triangles.

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
• Upper tails via high moments and entropic stability
• Large deviation for uniform graphs with given degrees
• Triangles in regular graphs with density below one half
• On the density of triangles and squares in regular finite and unimodular random graphs
• Typical large graphs with given edge and triangle densities

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)