μ_{r} = E X_{r} = (r n) 2^{- (2 r)}, L = lo g_{2} n .

Fix

0 < ε < 1

. At

r_{-} = ⌊(2 - ε) L ⌋

, the estimates

(r n) \geq (n / r)^{r}

and

r = O (L)

give

lo g_{2} μ_{r_{-}} \geq r_{-} L - \frac{r _{-} ( r _{-} - 1 )}{2} - r_{-} lo g_{2} r_{-} = (ε - \frac{ε ^{2}}{2}) L^{2} - O (L lo g L) .

This eventually exceeds

(9/5) L

. At

r_{+} = ⌈(2 + ε) L ⌉

, the upper bound

(r n) \leq n^{r}

instead gives

lo g_{2} μ_{r_{+}} \leq - (ε + \frac{ε ^{2}}{2}) L^{2} + O (L),

μ_{r_{+}} < n^{9/5}

. Moreover

\frac{μ _{r + 1}}{μ _{r}} = \frac{n - r}{r + 1} 2^{- r} < 1 (r \geq r_{+}),

so no later clique size can regain the threshold. The maximum defining

r_{0}

exists for sufficiently large

n

, since

μ_{2} = (2 n) /2 \geq n^{9/5}

then. We have

r_{-} \leq r_{0} < r_{+}

. Letting

ε

decrease to zero proves the asymptotic size:

r_{0} = (2 + o (1)) lo g_{2} n .

 Ancestors (10)

 Discussion (0)

There are no discussions about this article yet.

There are currently no matching articles.