I need to estimate the probability $P(\text{Graph G has at least 1 k-clique})$, any precision will do. I know the edge probability, say $p$, so the average number of the edges, $EK$, is $pm(m - 1)/2$, where $m$ is a number of vertices. I tried to use the Turan theorem with the Markov inequality, but Turan condition is too strong, so I ended up with the estimation $P(\text{Graph G has at least 1 k-clique}) \ge 0$.

I tried to use more precise Chebyshev inequality instead, but to calculate $E(K)^2$ is really hard in my case.

Does anyone know what should I do? Is there maybe any estimates for the probability of a k-clique in a random graph, so I could use it instead of precise Turan condition?

  • $\begingroup$ You haven't specified the random graph model you're using. Does every edge exist independently with probability $p$? $\endgroup$ – joriki May 6 '13 at 13:02
  • $\begingroup$ @joriki, unfortunately, the edges are not independent and the nature of dependency is really complicated $\endgroup$ – FrauHahnhen May 6 '13 at 13:36

If you fix the size of the graph, and vary $k$, then the probability is close to $1$ for small $k$, and close to $0$ for large $k$. There is a sharp drop at $k \approx r(p,n) = 2(\log n)/\log(1/p)$, which is the size of the largest clique in almost every random graph with $n$ vertices and edge probability $p$: the probability tends to be close to $1$ for $k < r(p,n)$, and close to $0$ for $k > r(p,n)$.

I don't think that generic inequalities are enough to establish this threshold; Bollobás in Section 11.1 of his Random Graphs textbook uses a pure counting argument (and is one source where the facts above can be found).

Another good source is the early article

  • B. Bollobás and P. Erdös, Cliques in random graphs, Math. Proc. Camb. Phil.Soc. 80, 1976, 419–427. doi:10.1017/S0305004100053056 (PDF)

which deals with the distribution in more detail. The Matula technical report (referenced by another answer) is also worth reading for its Example 1.

  • $\begingroup$ Thanks a lot. Is there any book or article I could reference to where this fact is proved? Or is it Random Graphs? $\endgroup$ – FrauHahnhen May 6 '13 at 15:42

The probability of any particular set of $k$ vertices forming a $k$-clique is $p^{\binom k2}$. The probability of there being at least one $k$-clique is less than the sum of all these probabilities, and thus less than $\displaystyle\binom mkp^{\binom k2}$.

I hope this is what you meant by "any precision will do" :-)

[Edit in response to the clarification:]

According to a comment under the question, the joint distribution of the existence of the edges is unknown and complicated. In this case nothing can be said about the probability of a $k$-clique; depending on the joint distribution this probability could lie anywhere between $0$ and $1$.


You can find a pretty good answer here: http://lyle.smu.edu/~matula/Tech-Report76.pdf

@joriki's bound makes an appearance.

Update: If the edges can be dependent, there are $k$-cliqueless graphs for any $p\le\frac{k-2}{k-1}$.

Let $\overline{K_r}$ be the edgeless graph on $r$ vertices, and let $K_{k-1}$ be the complete graph on $k-1$ vertices. Consider the product graph $K_{k-1}\square \overline{K_r}$. It has no $k$-clique, $r(k-1)$ vertices, each of degree $r(k-2)$. Hence there are $\frac{r^2(k-1)(k-2)}{2}$ edges, out of a maximum of $\frac{(rk-r)(rk-r-1)}{2}$, a fraction of approximately $\frac{k-2}{k-1}$. By making the product graph edges of equal and independent probability $\le 1$, any fraction in $[0,\frac{k-2}{k-1}]$ can be achieved as your $p$.

  • $\begingroup$ I'm afraid that only goes for independent edges $\endgroup$ – FrauHahnhen May 6 '13 at 13:40

Your Answer

