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 Collet and Eckmann from 2002 and considerably strengthens their observation that the triangles cannot be totally scattered in typical instances of regular graphs with many triangles.
@article{10_37236_10369,
author = {Pim van der Hoorn and Gabor Lippner and Elchanan Mossel},
title = {Regular graphs with many triangles are structured},
journal = {The electronic journal of combinatorics},
year = {2022},
volume = {29},
number = {1},
doi = {10.37236/10369},
zbl = {1481.05142},
url = {http://geodesic.mathdoc.fr/articles/10.37236/10369/}
}
TY - JOUR
AU - Pim van der Hoorn
AU - Gabor Lippner
AU - Elchanan Mossel
TI - Regular graphs with many triangles are structured
JO - The electronic journal of combinatorics
PY - 2022
VL - 29
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/10369/
DO - 10.37236/10369
ID - 10_37236_10369
ER -
%0 Journal Article
%A Pim van der Hoorn
%A Gabor Lippner
%A Elchanan Mossel
%T Regular graphs with many triangles are structured
%J The electronic journal of combinatorics
%D 2022
%V 29
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/10369/
%R 10.37236/10369
%F 10_37236_10369
Pim van der Hoorn; Gabor Lippner; Elchanan Mossel. Regular graphs with many triangles are structured. The electronic journal of combinatorics, Tome 29 (2022) no. 1. doi: 10.37236/10369
