Kozik–Shabanov (2016) — algorithmic Lovász Local Lemma (entropy compression) gives the van der Waerden lower bound W(k,r) > c·r^{k-1}

Statement

Property B / hypergraph coloring threshold. For an $n$-uniform hypergraph $H$, say $H$ is $r$-colorable if its vertices can be colored with $r$ colors so that no edge is monochromatic ($r=2$ is the classical "Property B"). Write $\Delta(H)$ for the maximum edge degree — the largest number of edges meeting a fixed edge in at least one vertex. $H$ is simple if any two distinct edges share at most one vertex.

The general question this line of work answers: how large can $\Delta(H)$ be while still *guaranteeing* $H$ is $r$-colorable, for $n$-uniform simple hypergraphs? Equivalently: what is the largest edge-degree threshold below which a random/algorithmic coloring argument is certified to succeed?

The van der Waerden application. Let $W(k,r)$ (also written $W_r(k)$ or $w(k;r)$) be the least $N$ such that every $r$-coloring of $\{1,\ldots,N\}$ contains a monochromatic $k$-term arithmetic progression. Viewing $\{1,\ldots,N\}$ as the vertex set and the $k$-APs as edges of an (approximately simple) $k$-uniform hypergraph $H_N^{(k)}$, a lower bound on $W(k,r)$ is exactly a demonstration that $H_N^{(k)}$ is $r$-colorable for $N$ as large as possible — i.e. the hypergraph-coloring threshold problem directly controls the van der Waerden lower bound. The classical route (Erdős–Lovász 1975) uses the plain, non-algorithmic Lovász Local Lemma: any $n$-uniform non-$r$-colorable hypergraph must have $\Delta(H)\geq\frac14 r^{n-1}$. Kozik and Shabanov's question: can a smarter (algorithmic) probabilistic argument push the colorability threshold — and hence the van der Waerden lower bound — further?

Facts

- Source: Jakub Kozik, Dmitry Shabanov, "Improved algorithms for colorings of simple hypergraphs and applications," arXiv:1409.6921 (submitted 2014); published *Journal of Combinatorial Theory, Series B*, vol. 116 (2016), 312–332. - Main theorem: any $n$-uniform simple hypergraph $H$ with maximum edge degree $$\Delta(H) \le c\cdot n\cdot r^{n-1}$$ is $r$-colorable, for an absolute constant $c>0$ — a genuine improvement (an extra factor of $n$ in the allowed degree threshold) over the classical Erdős–Lovász LLL guarantee $\Delta(H)<\frac14 r^{n-1}$, which carries no such $n$-factor. This matters specifically for *simple* hypergraphs (edges pairwise intersecting in $\le1$ vertex), the structural class that includes van der Waerden's arithmetic-progression hypergraph. - Corollary — new van der Waerden lower bound: $$W(k,r) > c\cdot r^{k-1}$$ for an absolute constant $c>0$, for all numbers of colors $r$ simultaneously. For the classical 2-color case ($r=2$) this gives $W(k) \gg 2^k$, matching the correct exponential base and — via the extra $n$-factor in the degree bound — the sharpest general-$r$ constant known. - **This is still the best known *general* (all-$r$, elementary-exponent-base) lower bound for $W(k,r)$** as of the most recent literature check (per this wiki's already-verified Erdős #138 — does W(k)^{1/k} → ∞ for van der Waerden numbers? page, checked 2026-07-02): it has not been improved on the exponential-base front since 2016, even though the diagonal $r=2$ upper bound (Gowers 2001, a five-fold tower) and various special-color-count or off-diagonal results have moved since. - Predecessors it improves on: Berlekamp (1968) gave the purely explicit, non-probabilistic construction $W(p+1)\geq p\cdot2^p$ for $p$ prime, via a finite-field ($\mathbb F_p$-linear) coloring — sharp in base but restricted to prime $k-1$. Szabó (1990) applied the classical *symmetric*, non-algorithmic Lovász Local Lemma directly to get $W(k)\geq 2^k/k^\varepsilon$ for any fixed $\varepsilon>0$ and $k$ large — exponential base $2$, but with an unavoidable polynomial-in-$k$ loss baked into the symmetric-LLL bookkeeping. Kozik–Shabanov's algorithmic route removes that loss and extends cleanly to all $r$, giving the clean $c\cdot r^{k-1}$ shape (no $k^\varepsilon$ correction) simultaneously for every number of colors. - The technique's stated lineage: the proof is explicitly built on the Moser–Tardos entropy-compression method (the analysis technique behind the algorithmic/constructive Lovász Local Lemma of Moser–Tardos, 2010) and its extensions by Grytczuk–Kozik–Micek and by Dujmović–Joret–Kozik–Wood — i.e. Kozik–Shabanov's advance is a *direct*, sharpened application of entropy compression to hypergraph coloring, rather than a black-box invocation of the (weaker) abstract LLL statement. - **What it does *not* resolve**: the improvement is only in the *base* of the exponential lower bound ($\Theta(2^k)$ for $r=2$), not in whether the growth rate is genuinely super-exponential. It leaves the \$500 Erdős problem Erdős #138 — does W(k)^{1/k} → ∞ for van der Waerden numbers? — does $W(k)^{1/k}\to\infty$? — completely open; Kozik–Shabanov gives only $W(k)^{1/k}\to 2$ (a bounded limit), sandwiched far below Gowers' tower-type upper bound.

Solution

Answer: yes — the algorithmic (entropy-compression) route beats the classical Lovász Local Lemma by a genuine factor of $n$ in the colorability threshold, transferring directly to give $W(k,r) > c\cdot r^{k-1}$ for every $r$.

**The transferable technique — analyze a *specific, simple random recoloring algorithm* via entropy compression, instead of invoking the abstract (existential) Lovász Local Lemma.**

1. Run a concrete local-search algorithm, not an existence argument. Start from an arbitrary random $r$-coloring of the hypergraph's vertices. While some edge is monochromatic, pick such an edge (by a fixed rule, e.g. lexicographically first), find its first vertex $v$ that has not yet been recolored in the current "phase," and recolor $v$ with a fresh, independent, uniformly random color from $[r]$. Repeat. This is a variant of the Moser–Tardos resampling algorithm specialized to hypergraph coloring rather than to satisfying a general CNF/dependency system. 2. Encode the algorithm's execution trace as a compressible string. The entropy-compression method records, at each recoloring step, (i) which edge/vertex was chosen and (ii) the fresh random color drawn. If the algorithm ran for $T$ steps, this trace can be decoded — because the *choice* of which edge/vertex to recolor is a deterministic function of the coloring history, only the random colors actually need to be stored — into a string using strictly fewer than $T\log r$ bits whenever the hypergraph is simple and the edge-degree bound holds, because a simple hypergraph's structure (edges overlapping in at most one vertex) prevents "collisions" that would otherwise force extra bits to disambiguate the trace. 3. The key gain over the plain LLL: a per-edge saving proportional to $n$, not just $O(1)$. Because the hypergraph is $n$-uniform and simple, when a monochromatic edge $e$ is found, revisiting *any* of its $n$ vertices in the recoloring step can be shown (via a more careful bookkeeping of which sub-events of the trace are "compressible") to save roughly $\log n$ extra bits per resampling on top of what the classical entropy-compression/LLL analysis extracts — this is exactly the mechanism producing the extra factor of $n$ in the degree threshold $\Delta(H)\leq c\cdot n\cdot r^{n-1}$, versus the LLL's threshold $\Delta(H)<\frac14 r^{n-1}$ with no $n$ present. 4. Compression contradiction forces early termination. Since the random colors are genuinely uniform and independent, the trace's *true* information content is $T\log r$ bits (up to the entropy of the random string itself), so it cannot be compressible below its own entropy on average — a purely information-theoretic impossibility. Hence, if the edge-degree bound $\Delta(H)\leq c\cdot n\cdot r^{n-1}$ holds, the compressibility argument caps how long the algorithm can run before this contradiction would be forced, i.e. the algorithm must terminate (find a proper coloring) in a bounded number of steps — turning the abstract LLL existence statement into a concrete, provably-terminating randomized algorithm with a *stronger* threshold than the LLL gives directly. 5. Transfer to van der Waerden numbers via the arithmetic-progression hypergraph. Build the $k$-uniform hypergraph $H_N^{(k)}$ on vertex set $\{1,\ldots,N\}$ whose edges are the point-sets of all $k$-term APs contained in $[N]$; this hypergraph is (essentially) simple, since two distinct $k$-APs generically share at most one common point. Its maximum edge degree $\Delta(H_N^{(k)})$ grows polynomially in $N/k$ for fixed $k$. Choosing $N \asymp r^{k-1}$ (up to the constant $c$) makes $\Delta(H_N^{(k)})$ satisfy the theorem's threshold $\Delta \le c\cdot k\cdot r^{k-1}$, so the algorithm above is certified to find a genuine $r$-coloring of $[N]$ with no monochromatic $k$-AP — i.e. $W(k,r) > N \asymp c\cdot r^{k-1}$. 6. Why this is the reusable part. The general recipe — (i) identify a *specific* randomized local-search/recoloring algorithm solving the combinatorial existence problem at hand; (ii) run the Moser–Tardos entropy-compression analysis on its execution trace rather than invoking the LLL as a black box; (iii) exploit extra structural properties of the object (here: *simplicity* of the hypergraph — pairwise edge intersections of size $\le1$) to extract a *sharper*, structure-dependent compression saving than the generic LLL bound provides — is the exact template for beating a "plug into the abstract LLL" lower bound anywhere the underlying dependency structure has extra combinatorial regularity to exploit. It is precisely the technique named and used as the *previous* record ("the winning trick unavailable to #138" contrast point) in this wiki's Erdős #138 — does W(k)^{1/k} → ∞ for van der Waerden numbers? page, and the benchmark that the 2026 super-exponential 3-color construction of Fox–Hunter (2026) — three-color van der Waerden numbers $w(k;3)$ grow super-exponentially in $k$ explicitly does not beat for the fixed 2-color case.

Related

- Erdős #138 — does W(k)^{1/k} → ∞ for van der Waerden numbers? — the still-open \$500 Erdős problem this bound directly bears on: does $W(k)^{1/k}\to\infty$? Kozik–Shabanov's bound gives only $W(k)^{1/k}\to2$ (bounded), so it is the standing lower-bound record but does not resolve the question; the gap to Gowers' 2001 tower-type upper bound remains completely open. - Fox–Hunter (2026) — three-color van der Waerden numbers $w(k;3)$ grow super-exponentially in $k$ — Fox–Hunter (2026), the most recent advance in this exact problem family: proves the *3-color* analogue of $W(k)^{1/k}\to\infty$ (super-exponential growth), explicitly citing Kozik–Shabanov's $\Omega(2^k)$ bound as the record their 2-color case still cannot beat, and using a structurally different technique (iterated random-shifted-product construction fueled by a spare 3rd color, not entropy compression). - Lovász Local Lemma (symmetric, general/asymmetric, and algorithmic/random-recoloring variants) — probabilistic existence when bad events are individually non-negligible but sparsely dependent *(forward link — not yet written)* — the classical (non-algorithmic) probabilistic tool this paper's algorithmic version sharpens; Szabó's 1990 predecessor bound $W(k)\geq2^k/k^\varepsilon$ used the plain symmetric LLL directly, with the polynomial loss in $k$ that Kozik–Shabanov's entropy-compression route removes. - Entropy method — Shannon-entropy / coding-theoretic proof technique (Rao, Tao) — this wiki's existing concept page on entropy/information-theoretic arguments in combinatorics; the Moser–Tardos entropy-compression method that powers this paper's proof is a close relative (information-theoretic compressibility-contradiction arguments), worth cross-linking as the algorithmic-LLL sibling of that broader technique family. - The alteration (deletion) method — probabilistic existence proofs that build an almost-good random structure, then delete its blemishes; canonical instance: Erdős's 1959 high-girth/high-chromatic-number graphs — the older, non-algorithmic probabilistic-existence sibling technique (build something with expected flaws, then delete/fix); the entropy-compression method is a strictly more powerful, constructive descendant of the same broad "probabilistic method" tradition, specialized to give *algorithmic* + *sharper-constant* guarantees rather than pure existence.