Abstract We consider the question of how many edge-disjoint near-maximal cliques may be found in the dense Erdős-Rényi random graph G (n, p). Recently Acan and Kahn showed that the largest such family contains only O (n²/ (n) ³) O (n 2 / (log n) 3) cliques, with high probability, which disproved a conjecture of Alon and Spencer. We prove the corresponding lower bound, (n²/ (n) ³) Ω (n 2 / (log n) 3), by considering a random graph process which sequentially selects and deletes near-maximal cliques. To analyse this process we use the Differential Equation Method. We also give a new proof of the upper bound O (n²/ (n) ³) O (n 2 / (log n) 3) and discuss the problem of the precise size of the largest such clique packing.
Griffiths et al. (Mon,) studied this question.