5
$\begingroup$

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?

$\endgroup$
  • $\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
4
$\begingroup$

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.

$\endgroup$
  • $\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
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

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

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.