Conjectured lower bound for near-maximal clique packings

Let G(n,p)G(n,p) be the Erdős–Rényi random graph, let p(0,1)p\in(0,1) and CN3C\in\mathbb{N}_{\geq 3} be constants, and let k0k_0 be the least integer such that the expected number of k0k_0-cliques in G(n,p)G(n,p) is less than 11. Set k=k0Ck=k_0-C. An edge-disjoint kk-clique packing is a collection of kk-cliques no two of which share an edge. Write γ\gamma for the exponent governing the expected number of kk-cliques, as in the source. Near-maximal clique-packing conjecture. With high probability, G(n,p)G(n,p) contains at least

2(γ2o(1))pn2lognk4\frac{2(\gamma-2-o(1))pn^2\log n}{k^4}

edge-disjoint kk-cliques. This conjecture concerns the expected duration of the random clique-removal process; the paper's method is intended to establish the corresponding lower bound, while the optimal packing size remains uncertain.

Sources & referencesView supporting material

Primary source

Simon Griffiths and Letícia Mattos, “Clique packings in random graphs”, arXiv:2405.00667 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.