Sparse random graphs with many triangles

Suman Chakraborty, Remco van der Hofstad, Frank den Hollander

Published 2021-12-13, updated 2022-02-17Version 2

In this paper we consider the Erd\H{o}s-R\'enyi random graph in the sparse regime in the limit as the number of vertices $n$ tends to infinity. We are interested in what this graph looks like when it contains many triangles, in two settings. First, we derive asymptotically sharp bounds on the probability that the graph contains a large number of triangles. We show that conditionally on this event, with high probability the graph contains an almost complete subgraph, i.e., the triangles form a near-clique, and has the same local limit as the original Erd\H{o}s-R\'enyi random graph. Second, we derive asymptotically sharp bounds on the probability that the graph contains a large number of vertices that are part of a triangle. If order $n$ vertices are in triangles, then the local limit (provided it exists) is different from that of the Erd\H{o}s-R\'enyi random graph. Our results shed light on the challenges that arise in the description of real-world networks, which often are sparse, yet highly clustered, and on exponential random graphs, which often are used to model such networks.