Conjectured lower bound for near-maximal clique packings
Let be the Erdős–Rényi random graph, let and be constants, and let be the least integer such that the expected number of -cliques in is less than . Set . An edge-disjoint -clique packing is a collection of -cliques no two of which share an edge. Write for the exponent governing the expected number of -cliques, as in the source. Near-maximal clique-packing conjecture. With high probability, contains at least
edge-disjoint -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
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.