Conjectured lower bound for near-maximal clique packings
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.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.