Regular graphs with many triangles are structured
type: Item
instance of: scholarly article
title: Regular graphs with many triangles are structured
zbMATH Open document ID: 1481.05142
DOI: 10.37236/10369
author: Gabor Lippner
author: Elchanan Mossel
author: Pim Van der Hoorn
published in: The Electronic Journal of Combinatorics
publication date: 2022-02-01T00:00:00Z
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.
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 60C05
zbMATH DE Number: 7467800
zbMATH Keywords: structural stability
zbMATH Keywords: large deviations
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.37236/10369
OpenAlex ID: W4210467702
cites work: On the large deviations of traces of random matrices
cites work: The missing log in large deviations for triangle counts
cites work: Nonlinear large deviations
cites work: The large deviation principle for the Erdős-Rényi random graph
cites work: The number of large graphs with a positive density of triangles
cites work: Large deviations of subgraph counts for sparse Erdős-Rényi graphs
cites work: Upper tails for triangles
cites work: Upper tails for subgraph counts in random graphs
cites work: The infamous upper tail
cites work: The deletion method for upper tail estimates
cites work: Bipodal Structure in Oversaturated Random Graphs
cites work: The phases of large networks with edge and triangle constraints
cites work: Small subgraphs of random regular graphs
cites work: Divide and conquer martingales and the number of triangles in a random graph
cites work: On replica symmetry of large deviations in random graphs
cites work: On the variational problem for upper tails in sparse random graphs
cites work: Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
cites work: The asymptotics of large constrained graphs
cites work: Phase transitions in a complex network
cites work: A large deviation result on the number of small subgraphs of a random graph
description: scientific article; zbMATH DE number 7467800