Clique coverings of the edges of a random graph (Q2367438): Difference between revisions

Bounds on the clique number of the random graph (with the edge probability of 1/2) are derived. It is proved that almost every graph with \(n\) vertices has a collection of \(O(n^2\ln\ln n/(\ln n)^2)\) cliques that cover all its edges. It is also proved that for almost every graph with \(n\) vertices, in order to cover all its edges it is necessary to use at least \((1-\varepsilon)n^2/(2\ln n)^2\) cliques.