Regular graphs with many triangles are structured

Pim van der Hoorn, Gabor Lippner, Elchanan Mossel

Research output: Contribution to journalArticleAcademicpeer-review

19 Downloads (Pure)

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 languageEnglish
Article numberP1.7
Number of pages16
JournalThe Electronic Journal of Combinatorics
Volume29
Issue number1
DOIs
Publication statusPublished - 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)

Fingerprint

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

Cite this