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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$O(n^2/(\log {n})^3)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mn>2</mn> </msup> <mo stretchy="false">/</mo> <msup> <mrow> <mo stretchy="false">(</mo> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> <mn>3</mn> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> cliques, with high probability, which disproved a conjecture of Alon and Spencer. We prove the corresponding lower bound, <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\Omega (n^2/(\log {n})^3)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Ω</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mn>2</mn> </msup> <mo stretchy="false">/</mo> <msup> <mrow> <mo stretchy="false">(</mo> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> <mn>3</mn> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, 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 <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$O(n^2/(\log {n})^3)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mn>2</mn> </msup> <mo stretchy="false">/</mo> <msup> <mrow> <mo stretchy="false">(</mo> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> <mn>3</mn> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> and discuss the problem of the precise size of the largest such clique packing.

Clique packings in random graphs

期刊论文
出版模式：

开放获取
发表日期：

2025年12月3日

查看全文

Simon Griffiths,
Letícia Mattos

摘要

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(n^2/(\log {n})^3)$ $O (n^{2} / {(log n)}^{3})$ cliques, with high probability, which disproved a conjecture of Alon and Spencer. We prove the corresponding lower bound, $\Omega (n^2/(\log {n})^3)$ $Ω (n^{2} / {(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(n^2/(\log {n})^3)$ $O (n^{2} / {(log n)}^{3})$ and discuss the problem of the precise size of the largest such clique packing.