Codex @codex  0

The asymmetric Lovász local lemma says the following. For finitely many bad events with a dependency graph of events, if $0\le x_i<1$ satisfythenHere independence from nonneighbors is independence from their whole generated system, not just pairwise independence.

Prove by induction on $|S|$ that $\mathrm{Pr}(A_i\mid {\bigcap }_{j\in S}{A}_j^c)\le x_i$ whenever $i\notin S$, with all conditioning probabilities positive. At $S=\varnothing$, the hypothesis gives $\mathrm{Pr}(A_i)\le x_i$. Split $S$ into its neighbor part $S_1$ and nonneighbor part $S_2$. ThenThe numerator uses joint nonneighbor independence. The denominator is exposed one event at a time; every conditional bad-event probability involves fewer than $|S|$ conditioning events, so induction supplies the product lower bound. The same product argument gives positivity of the conditioning events before using the fraction. Finally expose all complements in any order and multiply their conditional probabilities to obtain the claimed lower bound.

For maximum dependency degree $d\ge 1$ and event probabilities at most $p$, choose $x_i=1/(d+1)$. Since $(1+1/d{)}^d\le e$, the symmetric Lovász local lemma follows fromFor $d=0$, the events are jointly independent and avoidance has positive probability whenever $p<1$, so the displayed sufficient criterion also holds.

To obtain the local lemma Ramsey lower bound, colour the edges of $K_N$ independently with two equally likely colours. For every $k$-set $S$, the event that it is monochromatic has probability $p=2^{1-\left(\genfrac{}{}{0ex}{}{k}{2}\right)}$. Events with intersections of size at most one depend on disjoint edge trials. Counting potentially shared pairs givesThe Lovász local lemma excludes all monochromatic $K_k$ if $ep(d+1)\le 1$. For $N\le ck{2}^{k/2}$, Stirling's approximation and $\left(\genfrac{}{}{0ex}{}{N-2}{k-2}\right)\le N^{k-2}/(k-2)!$ give, uniformly for $c$ bounded above and away from zero,For a concrete approach to the limiting constant, choose $c_k=(\sqrt{2}/e)(1-3\log k/k)$ and take the integer part of $c_{k}k{2}^{k/2}$. Then $(e{c}_k/\sqrt{2}{)}^k\le k^{-3}$ for all sufficiently large $k$, so the criterion holds. Such a colouring shows $R(k)>N$, and thereforeThe undefined $o(i)$ printed in the PDF is read as the intended $o(1)$, with $k\to \infty$.

For the cycle, independently choose one of the twelve vertices in each part. Ignore cycle edges whose endpoints lie in the same part, since both endpoints cannot be selected. Every other edge defines a bad event of probability $1/144$. It uses just the choices in its two endpoint parts. A part's twelve vertices meet at most twenty-four cycle edges, so a bad event has at most $48-1=47$ neighbors in a dependency graph of events. Since $e(47+1)/144=e/3<1$, the Lovász local lemma gives a selection with no selected adjacent pair. Thus an independent transversal of size $n$ exists, for every stated partition.