Clique packings in random graphs
We consider the question of how many edge-disjoint near-maximal cliques may be found in the dense Erdős-Rényi random graph G(n, p). Recently Acan and Kahn showed that the largest such family contains only O(n2/(log n)3) cliques, with high probability, which disproved a conjecture of Alon and Spenc...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article (Journal) |
| Language: | English |
| Published: |
3 December 2025
|
| In: |
Combinatorica
Year: 2025, Volume: 45, Issue: 6, Pages: 1-48 |
| ISSN: | 1439-6912 |
| DOI: | 10.1007/s00493-025-00188-6 |
| Online Access: | Verlag, kostenfrei, Volltext: https://doi.org/10.1007/s00493-025-00188-6 Verlag, kostenfrei, Volltext: https://link.springer.com/article/10.1007/s00493-025-00188-6 
|
| Author Notes: | Simon Griffiths, Letícia Mattos |
| Summary: | We consider the question of how many edge-disjoint near-maximal cliques may be found in the dense Erdős-Rényi random graph G(n, p). Recently Acan and Kahn showed that the largest such family contains only O(n2/(log n)3) cliques, with high probability, which disproved a conjecture of Alon and Spencer. We prove the corresponding lower bound, Ω(n2/(log n)3), by considering a random graph process which sequentially selects and deletes near-maximal cliques. To analyse this process we use the Differential Equation Method. We also give a new proof of the upper bound O(n2/(log n)3) and discuss the problem of the precise size of the largest such clique packing. |
|---|---|
| Item Description: | Gesehen am 24.02.2026 |
| Physical Description: | Online Resource |
| ISSN: | 1439-6912 |
| DOI: | 10.1007/s00493-025-00188-6 |