Let u(n,p,k) be the k-clique packing number of the random graph G(n,p), that is, the maximum number of edge-disjoint k-cliques in G(n,p). In 1992, Alon and Spencer conjectured that for p = 1/2 we have u(n,p,k) = Ω(n²/k²) when k = k(n,p) - 4, where k(n,p) is minimum t such that the expected number of t-cliques in G(n,p) is less than 1. This conjecture was disproved a few years ago by Acan and Kahn, who showed that in fact u(n,p,k) = O(n²/k³) with high probability, for any fixed p ∈ (0,1) and k = k(n,p) - O(1).
In this talk, we show a lower bound which matches Acan and Kahn's upper bound on u(n,p,k) for all p ∈ (0,1) and k < k(n,p) - 3. To prove this result, we follow a random greedy process and use the differential equation method. This is a joint work with Simon Griffiths and Rob Morris.
Contact Sean at SEnglish (at) illinois (dot) edu for Zoom information.