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...
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Dokumenttyp: | Article (Journal) |
| Sprache: | Englisch |
| Veröffentlicht: |
3 December 2025
|
| In: |
Combinatorica
Year: 2025, Jahrgang: 45, Heft: 6, Pages: 1-48 |
| ISSN: | 1439-6912 |
| DOI: | 10.1007/s00493-025-00188-6 |
| Online-Zugang: | 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 
|
| Verfasserangaben: | Simon Griffiths, Letícia Mattos |
| Zusammenfassung: | 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. |
|---|---|
| Beschreibung: | Gesehen am 24.02.2026 |
| Beschreibung: | Online Resource |
| ISSN: | 1439-6912 |
| DOI: | 10.1007/s00493-025-00188-6 |