 Growing-clique overlap bound

ID: growing-clique-overlap-bound

Write

μ_{r} = (r n) p^{(2 r)}

and

T_{s} = (s r) (r - s n - r) p^{- (2 s)} / (r n)

. The first mean condition implies

p^{- 1} \leq (e n / r)^{2/ (r - 1)}

eventually. For

2 \leq s \leq r /2

, this yields

T_{s} \leq (C / s)^{s}

, and each fixed-

s

term tends to zero when

n \geq r^{3}

. The second mean condition implies

p \leq ((r + 1) / n)^{2/ r}

eventually. Writing

s = r - j

gives

T_{r - j} = μ_{r}^{- 1} (j r) (j n - r) p^{j (2 r - j - 1) /2} \leq μ_{r}^{- 1} (C / j)^{j}

for

1 \leq j \leq r /2

, and

T_{r} = μ_{r}^{- 1}

. Both bounding series are summable. The overlap formula for the variance of a clique count therefore gives relative variance tending to zero; the second moment method proves an

r

 New to topics? Read the docs here!