Regular graphs with many triangles are structured

Pim van der Hoorn, Gabor Lippner, Elchanan Mossel

Research output: Contribution to journalArticleAcademicpeer-review


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.

Original languageEnglish
Article numberP1.7
Number of pages16
JournalThe Electronic Journal of Combinatorics
Issue number1
Publication statusPublished - 28 Jan 2022


Dive into the research topics of 'Regular graphs with many triangles are structured'. Together they form a unique fingerprint.

Cite this