Regular graphs with linearly many triangles

MaRDI QIDQ6316658zbMATH OpenFDO

Authors Pim Van der Hoorn, Gabor Lippner, Elchanan Mossel

Publication date 3 April 2019

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Enumeration in graph theory (05C30) Structural characterization of families of graphs (05C75)

Abstract: A $d$-regular graph on $n$ nodes has at most $T_{max}=fracn3binomd2$ triangles. We compute the leading asymptotics of the probability that a large random $d$-regular graph has at least $ccdot{T}_{max}$ 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.

This page was built for publication: Regular graphs with linearly many triangles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6316658)