Probability of a graph having at least 1 k-clique

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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.