Clique packings in random graphs

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²/(log 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²/(log 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²/(log n)³) O ( n 2 / ( log n ) 3 ) and discuss the problem of the precise size of the largest such clique packing.