Abstract
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 language | English |
---|---|
Article number | P1.7 |
Number of pages | 16 |
Journal | The Electronic Journal of Combinatorics |
Volume | 29 |
Issue number | 1 |
DOIs | |
Publication status | Published - 28 Jan 2022 |
Funding
∗Supported by ARO grant W911NF1610391. †Supported by ARO grant W911NF1610391 and NSF grant DMS 1800738. ‡Supported by NSF grant DMS-1737944, Vannevar Bush Faculty Fellowship ONR-N00014-20-1-2826, ONR grant N00014-17-1-2598, Simons Investigator award (622132)