The Erdős--Rényi random graph conditioned on every component being a clique

Abstract

We consider an Erdős-Rényi random graph conditioned on the rare event that all connected components are fully connected. Such graphs can be considered as partitions of vertices into cliques. Hence, this conditional distribution defines a distribution over partitions. Using tools from analytic combinatorics, we prove limit theorems for several graph observables: the number of cliques; the number of edges; and the degree distribution. We consider several regimes of the connection probability p as the number of vertices n diverges. We prove that there is a phase transition at p=1/2 in these observables. We additionally study the near-critical regime as well as the sparse regime.