Covering the edges of a random graph by cliques (Q1906846)

Asymptotic behavior of the clique cover number \(\Theta_1\) of a random graph is established. It is proved that there exist constants \(c_1(p)> 0\) and \(c_2(p)> 0\) such that with probability \(1- o(1)\) as \(n\to \infty\): \[ {c_1 n^2\over (\ln n)^2}\leq \Theta_1(G_{n, p})\leq {c_2 n^2\over (\ln n)^2}. \] This result answers in positive a conjecture by Bollobás, Erdös and Spencer.