Regular graphs with many triangles are structured (Q2073296)

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.