Key points are not available for this paper at this time.
We consider the question of how many edge-disjoint near-maximal cliques may be found in the dense Erdos-R\'enyi random graph G (n, p). Recently Acan and Kahn showed that the largest such family contains only O (n²/ (n) ³) cliques, with high probability, which disproved a conjecture of Alon and Spencer. We prove the corresponding lower bound, (n²/ (n) ³), 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) ³) and discuss the problem of the precise size of the largest such clique packing.
Griffiths et al. (Wed,) studied this question.