 Local lemma Ramsey lower bound

ID: local-lemma-ramsey-lower-bound

In an independent random two-colouring of

K_{N}

, a given

k

-vertex set is monochromatic with probability

2^{1 - (2 k)}

. Events on sets intersecting in at most one vertex use disjoint edges. Thus dependency degree is at most

(2 k) (k - 2 N - 2)

. The Lovász local lemma gives a colouring avoiding all monochromatic

K_{k}

when

e 2^{1 - (2 k)} (1 + (2 k) (k - 2 N - 2)) \leq 1

. For

N = c k 2^{k /2}

the expression is

O (k^{3/2} (ec / 2)^{k})

c

tending sufficiently slowly to

2 / e

proves

R (k) \geq (2 / e + o (1)) k 2^{k /2}

 New to topics? Read the docs here!