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?

  • $\begingroup$ Does a clique of size greater than $m$ count? $\endgroup$ – paw88789 Mar 2 at 18:27
  • $\begingroup$ If $G$ has a clique of size greater than $m$, than it also has a clique of size $m$, so yes. $\endgroup$ – wafs Mar 2 at 18:29
  • $\begingroup$ Is it a simple graph or can it contain parallel edges? $\endgroup$ – frabala Mar 2 at 18:40
  • $\begingroup$ It is simple. I'll add it to the question, thanks. $\endgroup$ – wafs Mar 2 at 18:47
  • $\begingroup$ 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. $\endgroup$ – Mike Earnest Mar 2 at 21:01

Your Answer

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

Browse other questions tagged or ask your own question.