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.
Pim van der Hoorn
1
;
Gabor Lippner
2
;
Elchanan Mossel
3
1
TU Eindhoven
2
Harvard University
3
MIT
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
@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
