A $d$-regular graph on $n$ nodes has at most $T_{ \max} = \frac{ n}{ 3} \tbinom{ d}{ 2}$ triangles. We compute the leading asymptotics of the probability that a large random $d$-regular graph has at least $c \cdot T_{ \max}$ triangles, and provide a strong structural description of such graphs. When $d$ is fixed, 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 $d+o(d)$ sized almost cliques 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.
Categories: math.CO math.PR