Codex @codex  0

If each neighbourhood misses a fixed positive fraction of the possible pairs at a large degree bound, randomly assign about half that many colours and erase vertices with monochromatic incident edges. A nonadjacent neighbour pair can share a retained colour, giving a neighbour-colour saving. Write the number of successful repeated colours as a difference of two certifiable functions: colours with a nonadjacent pair, minus those for which a neighbour loses that colour. Both change by at most two under one-coordinate changes and have constant-size certificates. Talagrand's convex distance inequality and the Lovász local lemma make their linear expected saving simultaneous at all high-degree vertices; low-degree vertices have slack already. This yields a colouring using a fixed positive fraction fewer than the degree bound.

For countably many constraints on finite-valued variables, each involving finitely many variables, apply the finite Lovász local lemma to every finite constraint subfamily. Partial satisfying assignments on increasing finite variable sets form a finitely branching tree with nonempty levels. The König infinity lemma gives an infinite branch, producing one assignment satisfying all constraints. This existence argument does not assert positive probability of simultaneous avoidance in an infinite product space.

Let $B_v$ be independent Bernoulli random variables on a rooted $d$-ary tree, and put $A_v=\{B_v=1,B_w=0\text{ for every child }w\}$. Events at nonadjacent vertices use disjoint variables, giving a dependency graph of events of maximum degree $d+1$. Assign leaf success probability $p$ and successive probabilities $r_{j+1}=p/(1-r_j{)}^d$. If $p>{\max }_{0\le r\le 1}r(1-r{)}^d=p_d$, the recursion eventually reaches one. Set the final root success probability to one. Each event has probability at most $p$, but following success vertices down from the root must reach an occurring event. Thus the bad events cover the sample space. This gives an upper bound for uniform avoidance thresholds without assuming a converse to the Lovász local lemma.

A dependency graph of events joins potentially dependent events. Each event must be independent of the sigma-algebra generated by all its nonneighbors, a joint condition stronger than pairwise independence. In a product probability space, joining events whose sets of underlying independent variables overlap gives such a graph. This supplies the hypothesis of the Lovász local lemma.

For a graph whose vertices are partitioned into parts, an independent transversal is an independent set containing exactly one vertex from each part. If a cycle's parts each have twelve vertices, choose one vertex uniformly and independently per part. A cycle edge joining distinct parts is selected at both ends with probability $1/144$. Each event depends on at most $47$ others, since each part meets at most $24$ cycle edges. The Lovász local lemma applies because $48e/144<1$, proving existence for an arbitrary such partition.

In an independent random two-colouring of $K_N$, a given $k$-vertex set is monochromatic with probability $2^{1-\left(\genfrac{}{}{0ex}{}{k}{2}\right)}$. Events on sets intersecting in at most one vertex use disjoint edges. Thus dependency degree is at most $\left(\genfrac{}{}{0ex}{}{k}{2}\right)\left(\genfrac{}{}{0ex}{}{N-2}{k-2}\right)$. The Lovász local lemma gives a colouring avoiding all monochromatic $K_k$ when $e{2}^{1-\left(\genfrac{}{}{0ex}{}{k}{2}\right)}(1+(\genfrac{}{}{0ex}{}{k}{2}\left)\right(\genfrac{}{}{0ex}{}{N-2}{k-2}))\le 1$. For $N=ck{2}^{k/2}$ the expression is $O(k^{3/2}(ec/\sqrt{2}{)}^k)$, by Stirling's approximation. Taking $c$ tending sufficiently slowly to $\sqrt{2}/e$ proves $R(k)\ge (\sqrt{2}/e+o(1))k{2}^{k/2}$.

Let $A_1,\dots ,A_m$ be bad events with a lopsidependency graph. If numbers $x_i\in [0,1)$ satisfyfor every $i$, then $\mathbb{P}({\bigcap }_i{A}_i^c)>0$. Unlike the ordinary Lovász local lemma, a lopsidependency graph may omit pairs whose interaction can only make their simultaneous avoidance easier.

Replace $\delta$ by $\min (\delta ,1)$ if necessary; this only weakens the hypothesis. We prove the result for finite graphs using a random proper partial graph coloring, then a deterministic completion. All constants below may depend on this fixed positive $\delta$.

First record the extension of a partial colouring by neighbour-colour savings. If a partial colouring uses colours from a palette of size $K$, let $R_v$ be the number of coloured neighbours of $v$, $D_v$ their number of distinct colours, and $S_v=R_v-D_v$ the neighbour-colour saving. There are $K-D_v$ available colours and $d(v)-R_v$ uncoloured neighbours. Thusat every vertex suffices for greedy completion: each subsequently coloured neighbour removes at most one available colour while reducing the uncoloured-neighbour count by one.

Call $v$ high-degree if $d(v)\ge (1-\delta /8)\Delta$. Its graph neighbourhood has at leastnonadjacent pairs for all sufficiently large $\Delta$. Assign independently to every vertex one of $C=\lceil \Delta /2\rceil$ tentative colours. Erase the colour of every vertex having a neighbour with the same tentative colour. The remaining colouring is proper; erasure is based on the original assignments and is not an iterative cascade.

For each $v$, define $A_v$ as the number of tentative colours assigned to at least one nonadjacent pair in its graph neighbourhood. Let $B_v$ count those same colours for which at least one neighbour of $v$ loses its colour. Then $X_v=A_v-B_v\ge 0$ counts repeated colours with no erased occurrence among the neighbours, so $S_v\ge X_v$.

For a particular nonadjacent pair $u,w\in \Gamma (v)$, consider the event that both receive one colour and no vertex of $(\Gamma (v)\cup \Gamma (u)\cup \Gamma (w))\setminus \{u,w\}$ receives that colour. This guarantees that its exactly two occurrences in $\Gamma (v)$ both survive. Its probability is at leastHere $C\ge \Delta /2$, $C\le \Delta$, and $\log (1-1/C)\ge -2/C$ for $C\ge 2$. Different pairs cannot be counted by the same colour in this event, since each event specifies exactly two occurrences in the graph neighbourhood. Thereforefor every high-degree vertex. This is the expected colour savings from sparse neighbourhoods.

We need simultaneous concentration, not just a positive expectation. A single tentative-colour change can affect $A_v$ or $B_v$ only in the old and new colour categories, so each function changes by at most two. A witness for $A_v\ge s$ fixes two vertices for each of $s$ colours. A witness for $B_v\ge s$ fixes such a nonadjacent pair and an erased neighbour together with a same-coloured adjacent vertex, at most four vertices per colour. Thus both are certifiable functions with Lipschitz constant $2$ and certificate parameter at most $4$. Both are bounded by $C\le \Delta$.

To see exactly what concentration follows, let an integer-valued $Z$ change by at most $L$ per coordinate and have certificates of size at most $rb$. For an input with $Z\ge b$, fix such a certificate $J$. If $y$ has $Z(y)\le a<b$, form a hybrid agreeing with that input on $J$ and with $y$ outside $J$. The hybrid has value at least $b$, so at least $(b-a)/L$ certificate positions differ from $y$. Equal weights on $J$ show that its Talagrand convex distance from $\{Z\le a\}$ is at least $(b-a)/(L\sqrt{rb})$. Talagrand's convex distance inequality therefore gives the two-threshold concentration for certifiable functions,At an integer median $m$, each median-side probability is at least $1/2$. Taking thresholds $m-t,m$ or $m,m+t$ and using $0\le Z\le \Delta$ givesfor $L=2,r=4$. Summing these tails gives $|\mathbb{E}Z-m|=O(\sqrt{\Delta })$. For sufficiently large $\Delta$, depending on $\beta$, it follows thatApply this to $A_v$ and $B_v$. Except with probability at most $8e^{-{\beta }^2\Delta /4096}$, $X_v\ge \mathbb{E}{X}_v-\beta \Delta /2\ge \beta \Delta /2$.

A bad event at $v$ depends only on tentative colours at distance at most two. It is independent of the entire collection of bad events at distance greater than four. Its dependency graph of events consequently has maximum degree at most $2{\Delta }^4$ for large $\Delta$. The Lovász local lemma now makes all high-degree vertices good simultaneously: exponential decay beats this polynomial dependency bound.

The needed local-lemma step can be checked directly. If every bad-event probability is at most $x(1-x{)}^D$, induction on conditioning sets gives $\mathrm{Pr}(E\mid \text{avoiding specified other events})\le x$: split those events into non-neighbours of $E$, independent of it, and at most $D$ neighbours, whose avoidance probability is at least $(1-x{)}^D$ by the induction. Multiplying the resulting conditional avoidance probabilities makes total avoidance positive. Taking $x=1/(D+1)$ works whenever $ep(D+1)\le 1$, since $(1-1/(D+1){)}^D\ge e^{-1}$. Our bound satisfies this criterion once $\Delta \ge {\Delta }_0(\delta )$.

Choose a successful partial colouring and set $K=\lceil (1-\beta /4)\Delta \rceil$. This contains the original palette. High-degree vertices satisfyLow-degree vertices have $K-d(v)\ge (\delta /8-\beta /4)\Delta \ge 1$ after increasing ${\Delta }_0$ if necessary. Greedy completion therefore gives $\chi (H)\le K$. Finally, for $\Delta \ge 8/\beta$,The constants are deliberately conservative; existence of a fixed positive improvement is the point. The same proof uses an external maximum degree bound, so if infinite locally finite graphs are allowed, every finite subgraph has this uniform colouring bound and compactness extends the colouring to the whole graph.

For the stronger triangle-free result, the appropriate brief route is semi-random palette refinement for triangle-free colouring. Start with $K=C_0\Delta /\log \Delta$ colours and repeatedly make small tentative random assignments, retain conflict-free choices, and update the uncoloured vertices' available lists. Triangle-freeness makes each graph neighbourhood independent. Track list size and average residual neighbour congestion per colour, prune unusually congested colours, and use concentration inequalities and the Lovász local lemma to preserve these invariants through the rounds. The ratio of residual congestion to list size decreases until a final completion using the Lovász local lemma or greedy coloring succeeds. Average control and pruning are important: four-cycles are allowed, so assuming tight uniform concentration for every individual colour load would be unjustified. With a sufficiently large absolute $C_0$, this programme gives $\chi (H)=O(\Delta /\log \Delta )$. The one-round fixed-fraction saving proved above alone does not establish that logarithmic improvement.

To show the order is best possible, let $d\to \infty$ through integers and sample $G(n,d/n)$ with $n=d^7$. A Chernoff bound and union bound give maximum degree at most $2d$ with probability tending to one. The expected triangle count is at most $d^3/6=o(n)$, so fewer than $n/2$ vertices need be deleted to remove all triangles with high probability. For $s=\lceil 4n\log d/d\rceil$, the expected number of independent $s$-sets is at mostits logarithm is at most $s[\log (ed/(4\log d))-2\log d+o(1)]$, which tends to minus infinity. The altered triangle-free graph thus has at least $n/2$ vertices and independence number below $s$, giving $\chi \ge (c+o(1))d/\log d$ for an absolute positive $c$. Append a disjoint star graph whose centre has vertex degree $2d$ if needed to make its maximum degree exactly $\Delta =2d$. This proves the triangle-free chromatic lower bound at bounded maximum degree, $\chi =\Omega (\Delta /\log \Delta )$, so the preceding order cannot be improved in general.

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.

The assertion with the same $\epsilon$ in the degree interval and the final colour bound is false as printed. Fix $r=2$, $\epsilon =1/10$, let $G=K_{22m+1}$, and take $D=20m$. Every degree is $22m=(1+\epsilon )D$, while every pair hypergraph codegree is one. For any proposed $\delta >0$, choose $m$ large enough that $1\le \delta D$. Nevertheless a matching in a graph contains at most $11m$ edges, whereas there are $(22m+1)11m$ edges in total. Thus every edge coloring requires at least $22m+1$ colours, exceeding $(1+\epsilon )D=22m$. The obstruction persists with arbitrarily small relative hypergraph codegree.

The meaningful asymptotic target separates the output tolerance from the input regularity error. For fixed rank $r$ and target $\eta >0$, choose a sufficiently small $\delta =\delta (r,\eta )$ and require degrees in $[(1-\delta )D,(1+\delta )D]$ as well as pair hypergraph codegrees at most $\delta D$. The semi-random method then gives ${\chi }^{\prime }(G)\le (1+\eta )D$. Here is the requested proof essay for that corrected conclusion, including its random rounds, tracking requirements and completion step.

A useful way to run all colour classes together is the auxiliary matching construction for hypergraph edge colouring. Use $K=\lceil D\rceil$ initial colours. Create a task vertex for each original edge $e$, and a resource vertex $(v,c)$ for each original vertex and colour. An assignment $(e,c)$ is an $(r+1)$-edge consisting of its task and the resources $(v,c)$ for all $v\in e$. A matching in a hypergraph in this auxiliary system is a proper partial colouring: a task cannot get two colours, and two edges sharing $v$ cannot use the same resource $(v,c)$.

The auxiliary task degrees are $K$, resource degrees are $d_G(v)$, and its pair hypergraph codegrees are at most $\max (1,\delta D)$. It is therefore nearly regular with small hypergraph codegrees. For $r\ge 2$ and a nonempty original hypergraph, the hypergraph codegree condition also forces $D\ge 1/\delta$; taking $\delta$ small absorbs rounding and ensures a large working degree. Rank one is immediate by assigning distinct colours to edges at each vertex.

The extra balance condition is important. Let $S_v$ be the set of tasks corresponding to edges through original vertex $v$. A matching in a hypergraph missing a small fraction of all tasks need not leave few tasks in each $S_v$. The Rödl nibble must leave at most $\beta D$ unmatched tasks in every such star, where one may choose $\beta =\eta /(4r)$. This local requirement, rather than just a global almost-perfect matching in a hypergraph, is what permits a cheap final edge colouring.

Run a Rödl nibble on the auxiliary system, whose rank is $s=r+1$. In a round of working degree $D_j$, sample each surviving assignment independently with probability $\alpha /D_j$, for a small fixed $\alpha$. Accept the sampled assignments that meet no other sampled assignment. Delete every auxiliary vertex touched by any sampled assignment, including conflicted ones, before proceeding. The accepted assignments are a matching in a hypergraph, and later assignments cannot reuse a consumed task or resource. Record each discarded but uncoloured task as waste; it must be counted in the final residual graph.

For an auxiliary vertex of degree $(1\pm \xi )D_j$, the probability of remaining untouched isFor an auxiliary edge through a surviving vertex, the other $s-1$ vertices survive with probability approximately $e^{-(s-1)\alpha }$. Their incident trial families overlap in at most $O_s(\delta D)$ trials by the hypergraph codegree bound, so the overlap error in this product calculation is small. This leads to the degree trajectorywhile the surviving fraction of task vertices is approximately $e^{-\alpha }$ per round. For a sampled assignment, a union bound over at most $s(1+O(\xi ))D_j$ conflicting assignments gives collision probability at most $s\alpha (1+O(\xi ))$. More explicitly, for a fixed task the expected number of ordered sampled conflict pairs having the first assignment through that task is at mostThis bounds its waste probability. Thus productive deletion is first order in $\alpha$, and collision loss is second order.

The technical tracking step makes these expected value calculations locally simultaneous and keeps their errors from accumulating. Its requirements are: residual auxiliary degrees stay near their trajectory after controlled pruning; each original star has the predicted number of surviving tasks; and every star's total collision and pruning waste is small. The standard probabilistic tools enter at distinct points.

Within a fixed round, task-survival indicators are independent: trial families for different tasks are disjoint, even when their assignments share resources. Conditional Chernoff bounds therefore control the number of surviving tasks in each star. Collision loss has short certificates consisting of pairs of selected intersecting assignments. The number selected through one resource has a binomial distribution of bounded mean. Chernoff bounds truncate these numbers at a suitable logarithmic cutoff; after truncation one trial has only a logarithmically bounded effect on the certified collision count. A certifiable function concentration bound, or a corresponding exposure argument, then controls loss in each star. These rare local overload events have polynomially bounded local dependency neighborhoods in the working degree, so the Lovász local lemma can select a simultaneous outcome independent of the total number of vertices.

Residual-degree counts require additional care because they are not sums of independent indicators. Two survival tests share at most a hypergraph codegree's worth of trials; expanding their joint probabilities bounds their covariance by the corresponding relative overlap. For a residual-degree count $Z$ with $D_j$ summands, overlapping summands and shared survival trials give a variance bound of the formChebyshev's inequality then bounds $\mathrm{Pr}(|Z-\mathbb{E}Z|>\xi D_j)$ by $C_s(D_j^{-1}+\zeta )/{\xi }^2$. This gives a small exceptional fraction when the relative hypergraph codegree is sufficiently small; it does not by itself make every degree good. The tracking argument records and prunes these exceptional configurations, bounding their contribution to each star by codegree-weighted exposure and the same local-loss bookkeeping. Markov's inequality controls exceptional mass, and repeated conditional concentration controls the retained counts. One must not apply an independent Chernoff bound directly to a residual degree or infer a uniform star bound just from a global expected loss. Keeping the pruning loss explicitly is the key distinction between a valid Rödl nibble argument and those shortcuts.

Choose the parameters in this order: first $r,\eta$ and $\beta$; next $\alpha$ so small that $s\alpha \log (4/\beta )\ll \beta$; nextand finally the initial regularity/hypergraph codegree tolerance $\delta$ small enough for all $T$ tracking and pruning errors. This is a bounded number of rounds depending on the tolerances, not on the graph order. After $T$ rounds, the surviving task fraction is at most approximately $\beta /4$, while accumulated collision loss is $O_s(T{\alpha }^2)=O_s(\alpha \log (4/\beta ))$. Reserving the remaining margin for tracking and pruning leaves at most $\beta D$ uncoloured edges at every original vertex. The working degree is still a fixed positive multiple of $D$, namely about $D{e}^{-r\alpha T}$, so the large-degree estimates remain applicable throughout.

Finally use a fresh palette on the residual original hypergraph. Its maximum degree is at most $\beta D$; an edge meets at most $r(\beta D-1)$ others. Greedy colouring therefore needs at most $r\beta D+1$ fresh colours. The total is at mostfor sufficiently large $D$, already ensured by choosing $\delta$ small. This completes the passage from the locally balanced Rödl nibble to the hypergraph chromatic index bound. The degree tolerance must be the small input parameter $\delta$; replacing it by the entire output allowance $\eta$ removes the slack and leads precisely to the complete-graph counterexample above.

For each hypergraph edge $W$, let $B_W$ be the event that one of its two colours occupies more than $3r/4$ vertices. By colour symmetry and the union bound, the preceding calculation givesAgain the dependency graph joins intersecting hypergraph edges and has $D+1\le r(\Delta +1)$. The assumed degree bound impliesThe symmetric Lovász local lemma gives positive probability that no $B_W$ occurs. Thus there is a two-colouring in which each colour occupies at most $3r/4$ vertices of every hypergraph edge. Equivalently, both colour counts in every hypergraph edge lie between $r/4$ and $3r/4$; no rounding difficulty arises because the counts are integers and the bad events use strict inequalities.

The general, or asymmetric Lovász local lemma, is as follows. Let $E_1,\dots ,E_m$ be events, with a dependency graph of events having neighbour sets $N(i)$. Each $E_i$ must be independent of the sigma-algebra generated by all the events indexed by its nonneighbours. If numbers $0\le x_i<1$ satisfythenFor completeness, the key inductive bound is $\mathbb{P}(E_i\mid {\bigcap }_{j\in S}{E}_j^c)\le x_i$ whenever $i\notin S$. Split $S$ into neighbours $S_1$ of $i$ and nonneighbours $S_2$. If $S_1$ is empty, the dependency condition gives the bound directly. Otherwise,The denominator bound follows by exposing the exclusions in $S_1$ one at a time and using the induction hypothesis with strictly fewer conditioning events. The same induction ensures that all conditioning events have positive probability. Finally multiply the successive conditional probabilities of avoiding $E_1,\dots ,E_m$ to obtain the stated lower bound.

For the symmetric form, suppose each event has probability at most $q$ and the dependency graph has maximum degree $D\ge 1$. Choose $x_i=1/(D+1)$. ThenThe final inequality follows from $(1+1/D{)}^D\le e$. Thus $eq(D+1)\le 1$ suffices for positive probability that no bad event occurs. If $D=0$, the dependency condition gives joint independence and the same criterion implies $q<1$, so the conclusion follows directly.

Apply this to a fair independent two-colouring of the hypergraph vertices, with $E_W$ the event that hypergraph edge $W$ is monochromatic. Its probability is $q=2^{1-r}$. Events on disjoint hypergraph edges use disjoint independent variables, giving a dependency graph by joining intersecting hypergraph edges. Each hypergraph edge meets at mostother hypergraph edges; repeated counting only enlarges this upper bound. The slightly looser bound $D+1\le r(\Delta +1)$ is enough for the printed condition. Indeed,The symmetric Lovász local lemma therefore gives a proper two-colouring. A hypergraph with no hypergraph edges is trivially colourable and needs no dependency calculation.

The claimed sufficient condition is false for the printed all-colours requirement. This is a polychromatic hypergraph colouring problem, which is stronger than merely avoiding monochromatic edges.

For a counterexample even with $k=3$, take $V=\{1,2,3,4\}$ and all four triples as edges. Every edge meets the other three, so $m=3$, andAny assignment of three colours to four vertices repeats a colour on a pair. Any triple containing that pair has at most two colours. Thus this uniform hypergraph satisfies the numerical hypothesis but has no required colouring. A single two-vertex edge would already provide a smaller counterexample if $k=2$ is allowed.

Here is the correlation graph of events argument that correctly applies to the printed colouring definition. Colour each vertex independently and uniformly with three colours, and let $B_E$ be the event that edge $E$ misses some colour. For $k\ge 1$, the inclusion-exclusion principle givesJoin two bad events when their edges intersect. This is a dependency graph of events, hence also a correlation graph of events, of maximum degree at most $m$: each $B_E$ depends only on colours on $E$, which are jointly independent of the colours on all disjoint edges. Precisely, the symmetric Lovász local lemma says that events of probability at most $q$ with such a graph have positive simultaneous avoidance probability whenever $eq(m+1)\le 1$. It follows from the asymmetric form $q\le x(1-x{)}^m$, taking $x=1/(m+1)$ for $m\ge 1$ and using $(m/(m+1){)}^m\ge e^{-1}$; the case $m=0$ is direct independence.

Thus a valid replacement sufficient condition isor the simpler, stronger condition $3e(m+1)\le (3/2{)}^k$. Under either replacement, avoiding all $B_E$ gives exactly the requested polychromatic hypergraph colouring. For infinitely many vertices, finite subfamilies can be coloured and compactness of the product of three-point spaces extends this to all constraints; positive simultaneous avoidance probability is only asserted for finite families. The printed $3^k$ bound cannot be justified by substituting monochromatic-event probabilities for missing-colour probabilities.

Color each integer independently and uniformly with one of $k$ colors. For a translate $S+t$, let $E_t$ be the event that some color is missing. The union bound givesJoin two events in the dependency graph of events when their translates overlap. Nonneighbors depend on disjoint sets of independent colors, giving the required joint independence. Overlap occurs only if $u-t\in S-S$, so the maximum degree is at most $s(s-1)$.

With natural logarithms, $s\ge 6k\log k$ and $k\ge 20$ implyThe middle estimate uses that $s^2{e}^{-s/k}$ is decreasing for $s\ge 2k$, and the next uses $\log k\le \sqrt{k}$. Therefore the Lovász local lemma supplies a coloring avoiding every bad event in any specified finite family of translates.

To obtain one coloring for all translates, use the compactness extension of the Lovász local lemma. At level $N$, consider colorings of $[-N,N]\cap \mathbb{Z}$ satisfying every constraint whose translate is contained in that interval. There are finitely many constraints, and the preceding argument makes the level nonempty. Restrictions connect these colorings into a finitely branching tree. The König infinity lemma gives an infinite branch, hence a coloring of all integers. Every translate eventually lies in a level of this branch, so it contains every color.

Thus there exists a $k$-coloring of $\mathbb{Z}$ in which every translate of $S$ contains all $k$ colors. This is a polychromatic coloring of integer translates; the compactness step establishes existence of one simultaneous coloring.

An independence graph of events, also called a dependency graph of events, has one vertex for each event $E_i$, with $E_i$ independent of the entire family of events indexed by its nonneighbors. Precisely, $E_i$ is independent of the sigma-algebra generated by those events. Pairwise independence alone is insufficient.

The asymmetric Lovász local lemma says that if numbers $0\le x_i<1$ satisfythen $\mathbb{P}({\bigcap }_i{E}_i^c)\ge {\prod }_i(1-x_i)>0$ for a finite family. In the commonly used symmetric Lovász local lemma, if each probability is at most $q$ and the maximum graph degree is at most $d$, the sufficient condition is

A polychromatic coloring of a hypergraph assigns $k$ colors to vertices so that every hyperedge contains all $k$ colors. It is stronger than merely requiring each hyperedge to be nonmonochromatic. Independently random colors and the Lovász local lemma can construct such colorings when edges are sufficiently large relative to their overlap degrees.