0
$\begingroup$

Suppose we have a random graph with $n$ vertices and edges that are present independently with the probability $p$. What is the expectation of its clique number?

It is quite easy to calculate the expectation for small $n$-s. For example: if $n = 1$, then the answer is $1$, if $n=2$, then $1+p$, if $n = 3$, then $1 + 3p - 3p^2 + 2p^3$... However, I failed to find any general formula for arbitrary $n$.

Any help will be appreciated.

$\endgroup$
2
$\begingroup$

Probability distributions of clique numbers are an active area of research. Most of the known results are in terms of bounds or asymptotic behavior. The following might all be of interest:

Your problem can at least be reduced to an arguably simpler combinatorial problem. Let $a(n,k,c)$ denote the number of graphs with $n$ vertices, $k$ edges, and clique number $c$. Let $N(n)=\frac{n(n-1)}{2}$ be the total number of places one of those edges could be placed.

The probability of a graph having $k$ edges is modeled by the binomial distribution $$q(n,k)={N(n)\choose k}p^k(1-p)^{N(n)-k}.$$

The probability of a graph with $k$ vertices having clique number $c$ is $$r(n,k,c)=\frac{a(n,k,c)}{N(n)\choose k}.$$

The probability of a graph having $k$ edges AND having clique number $c$ is then $$\begin{aligned}b(n,k,c)&=r(n,k,c)q(n,k)\\&=a(n,k,c)p^k(1-p)^{N(n)-k}.\end{aligned}$$

To find the probability of having clique number $c$, we simply sum over the variable $k$ to obtain $$\begin{aligned}s(n,c)&=\sum_{k=0}^Nb(n,k,c)\\&=\sum_{k=0}^Na(n,k,c)p^k(1-p)^{N(n)-k}.\end{aligned}$$

The expected value follows the standard procedure. $$\begin{aligned}E(n)&=\sum_{c=1}^nc\cdot s(n,c)\\&=\sum_{c=1}^nc\sum_{k=0}^Na(n,k,c)p^k(1-p)^{N(n)-k}.\end{aligned}$$

The only really troublesome part is the combinatorial question. How does one count $a(n,k,c)$?

One of the neat properties that we discovered in this process though is that the solution is a polynomial of maximum degree $N(n)$ with integer coefficients. This suggests a relationship to generating functions and chromatic polynomials which might allow low-ordered versions to be reasoned about in terms of roots and other qualitative properties. The roots are kind of weird even for the small examples you presented, and this could easily be a dead end as well.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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