# Expected number of maximal cliques in $G(n,p)$

The $G(n,p)$ random graph model creates graphs with $n$ vertices and each possible edge exists independently with probability $p\in (0,1)$.

Much is known about the (expected) size of a largest clique in these graphs, and it has been shown that the expected number of maximal cliques of size $d$ is

$${n\choose d} p^{d \choose 2} (1-p^d)^{n-d}.$$

To find the expected number of maximal cliques, just sum over all values of $d$ to get

$$\mu (G(n,p)) := \sum_{d=1}^n {n\choose d} p^{d \choose 2} (1-p^d)^{n-d}.$$

I'm interested in the asymptotic growth of $\mu (G(n,p))$ as a function $n$. For example, if $p$ is fixed, does $\mu$ grow polynomially in $n$?

A quasi-polynomial bound is not hard to show. Since the expected maximum clique size is roughly $\omega(G(n,p))\approx\frac{2 \log n}{\log(1/p)}$, the number of cliques (not necessarily maximal) is $O( {n \choose \omega(G(n,p))+1}) = O(n^{\omega(G(n,p))+1})=O(n^{\frac{2 \log n}{\log(1/p)}+1})$.

• Do you really want $p$ fixed as $n \to \infty$? I always see these analyses done either in the limit that $np$ is fixed, that $p \propto n^{-\alpha}$ or that $p = c\log n/n$. – korrok May 28 '14 at 16:32
• @korrok Sure, why not. For gits and shiggles. – Austin Buchanan May 28 '14 at 16:39

Since $\mu$ is the sum of $n$ terms, we can estimate it up to a factor of $n$ by the maximal term: $$\max_{d=1}^n \binom{n}{d} p^{\binom{d}{2}} (1-p^d)^{n-d} \leq \sum_{d=1}^n \binom{n}{d} p^{\binom{d}{2}} (1-p^d)^{n-d} \leq n\max_{d=1}^n \binom{n}{d} p^{\binom{d}{2}} (1-p^d)^{n-d}.$$ In order to find out which term is the largest, we can use the estimate $$\log_2 \binom{n}{d} p^{\binom{d}{2}} (1-p^d)^{n-d} \approx nh(d/n) + \binom{d}{2} \log_2 p - (n-d)p^d,$$ which is true up to polynomial factors for $d = \omega(1)$. We can estimate the magnitude of the largest term by differentiating this quantity with respect to $d$. If you follow this path, you should obtain an estimate for $\mu$ which is tight up to polynomial factors in $n$.
• What is the term $h(d/n)$? – Austin Buchanan May 28 '14 at 20:24