Counting cliques in a random graph

2022/08/16 by Sakurai, Taro, Tokushige, Norihide
#05A16 #05C30 #05C80 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2208.07492

Abstract

We show that the expected number of cliques in the Erdős-Rényi random graph G(n,p) is n^\frac1-2log p(log n-2loglog n+O(1)).

Related

• Clique packings in random graphs
• Super-logarithmic cliques in dense inhomogeneous random graphs
• On some estimates for Erdös-Rènyi random graph
• The Erdős-Rényi Random Graph Conditioned on Every Component Being a Clique
• Pairwise disjoint maximal cliques in random graphs and sequential motion planning on random right angled Artin groups