2
$\begingroup$

I need to find the order of the minimum k = k(n) such that the probability of having at least 1 k-clique in a random graph $G(n, \frac{1}{2}$) is $\mathcal{O}(\frac{1}{n})$. $X_k$ is the random variable which count the number of k-cliques in a random graph. I already know $E[X_k] = \binom{n}{k}(\frac{1}{2})^{\binom{k}{2}}$. I don't know exactly how to find the exact value of k. I know $P[X_k \geq 1] \leq E[X_k]$ for Markov inequality but I'm not sure that this is helpful. Thanks in advance

$\endgroup$
3
$\begingroup$

The value is $2\log_2 n - 2\log_2\log_2 n + O(1)$.

Let $k_0$ be the maximal value such that the expected number of cliques of size $k_0$ is at least 1. A boring calculation shows that $k_0 = 2\log_2 n - 2\log_2\log_2 n + O(1)$. It is a classical result that with high probability, $G(n,1/2)$ contains a $(k_0-1)$-clique. This implies that $k > k_0-1$. On the other hand, it is known that the expected number of cliques of size $k_0+1+C$ is $O((\log n/n)^C)$ for any constant $C$ (this is because the expected number of cliques drops by $\Theta(\log n/n)$ near $k_0$). This shows that $k \leq k_0+3$. We conclude that $k_0 \leq k \leq k_0+3$.

You can probably decrease the length of this interval by 1, following the proof of the classical result which shows concentration of the clique number of two values rather than three.

$\endgroup$
  • $\begingroup$ Could you please clarify the calculation for $k_0$? And what is that classical result you mentioned? $\endgroup$ – Pratozoo Jan 14 '18 at 18:07
  • $\begingroup$ I skipped the calculation since it's very tiring. You can find the details in Random graphs by Frieze and Karonski. $\endgroup$ – Yuval Filmus Jan 14 '18 at 18:54
  • $\begingroup$ I couldn't find it, could you please just tell me the idea behind it? $\endgroup$ – Pratozoo Jan 14 '18 at 23:03
  • $\begingroup$ It's just a calculation. You have to push through it. See Lemma 9.1 here. $\endgroup$ – Yuval Filmus Jan 14 '18 at 23:04

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.