= Local lemma Ramsey lower bound
{title2=$R(k)\geq(\sqrt2/e+o(1))k2^{k/2}$}
In an independent random two-colouring of $K_N$, a given $k$-vertex <set> is monochromatic with <probability> $2^{1-\binom k2}$. <Events> on <sets> intersecting in at most one vertex use disjoint edges. Thus dependency degree is at most $\binom k2\binom{N-2}{k-2}$. The <Lovász local lemma> gives a colouring avoiding all monochromatic $K_k$ when $e\,2^{1-\binom k2}(1+\binom k2\binom{N-2}{k-2})\leq1$. For $N=ck2^{k/2}$ the expression is $O(k^{3/2}(ec/\sqrt2)^k)$, by <Stirling's approximation>. Taking $c$ tending sufficiently slowly to $\sqrt2/e$ proves $R(k)\geq(\sqrt2/e+o(1))k2^{k/2}$.
Back to article page
