# What is the probability that a random graph contains an $m$ clique.

Given a simple random graph $$G$$ with $$n$$ vertices where every edge is present with probability $$p$$ independently of the others, what is the probability that $$G$$ contains a clique of size $$m$$?

The probability that a particular set of $$m$$ vertices is a clique is $$p^{m \choose 2}$$ and there are $${n \choose m}$$ such sets, but the probability clearly isn't $${n \choose m}p^{m \choose 2}$$...so what do I do?

• Does a clique of size greater than $m$ count? – paw88789 Mar 2 at 18:27
• If $G$ has a clique of size greater than $m$, than it also has a clique of size $m$, so yes. – wafs Mar 2 at 18:29
• Is it a simple graph or can it contain parallel edges? – frabala Mar 2 at 18:40
• It is simple. I'll add it to the question, thanks. – wafs Mar 2 at 18:47
• You might want to look at math.stackexchange.com/questions/383235/… and some of the references there for asymptotic results/ bounds. I would not hold out hope for an exact answer. – Mike Earnest Mar 2 at 21:01