The Erdős--Rényi random graph conditioned on every component being a clique
Authors
- Gösgens, Martijn
ORCID: 0000-0002-6168-3517 - Lüchtrath, Lukas
ORCID: 0000-0003-4969-806X - Magnanini, Elena
ORCID: 0000-0001-5430-4884 - Noy, Marc
- de Panafieu, Élie
2020 Mathematics Subject Classification
- 05C80 60F05 11B73 05A18
Keywords
- Cluster graphs, set partitions, generating functions, limit theorems
DOI
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
Download Documents