6
$\begingroup$

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})$.

$\endgroup$
2
  • $\begingroup$ 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$. $\endgroup$ May 28, 2014 at 16:32
  • $\begingroup$ @korrok Sure, why not. For gits and shiggles. $\endgroup$ May 28, 2014 at 16:39

1 Answer 1

3
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ What is the term $h(d/n)$? $\endgroup$ May 28, 2014 at 20:24
  • $\begingroup$ @AustinBuchanan It's the binary entropy function. $\endgroup$ May 28, 2014 at 20:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.