Conjectured lower bound for near-maximal clique packings

About 2 years old · traced to

Let G(n,p)G(n,p) be the Erdős–Rényi random graph, let p∈(0,1)p\in(0,1) and C∈N≥3C\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=k0−Ck=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(γ−2−o(1))pn2log⁡nk4\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.

References

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.