2019/04/03 by Pim van der Hoorn, van der Hoorn, Pim, Gábor Lippner +3
Computer Science · Mathematics · #05C30 #05C75 #05C80 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.1904.02212
openalex publication_date 2019/04/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A d-regular graph on n nodes has at most Tmax = (n)/(3) \tbinomd2 triangles. We compute the leading asymptotics of the probability that a large random d-regular graph has at least c ⋅ Tmax 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.