Pigeonhole reductions between Ramsey-type functions (e.g. H(k) ≥ W(k-1,k))

Statement

The general pattern. Many "Ramsey-type functions" — numbers $f(\cdot)$ defined as the threshold $N$ at which every colouring (subject to some constraint) of a structure on $[N]$ is forced to contain some monochromatic, rainbow, or otherwise colour-patterned substructure — come in families indexed by how the colouring is constrained: the number of colours available, whether colours must be used exactly once each, whether repeats are allowed, etc. A pigeonhole reduction is a one-line argument that a colouring avoiding the target pattern *under a looser colour constraint* automatically avoids it *under a stricter one* (or vice versa), purely because of a counting obstruction on the number of colours — never using any structural property of the coloured objects themselves. This converts a lower bound on one member of the family directly into a lower bound (or, dually, an upper bound) on another member, with no extra combinatorial work beyond checking the colour-count arithmetic.

Canonical instance (Erdős–Graham canonical Ramsey function vs. van der Waerden number). Let $[N]=\{1,\dots,N\}$. For $k\ge2$ define: - $W(r,k)$ = the least $N$ such that every $r$-colouring $\chi:[N]\to[r]$ contains a monochromatic $k$-term arithmetic progression ($k$-AP) (van der Waerden's theorem, 1927, guarantees this is finite). - $H(k)$ = the least $N$ such that every colouring of $[N]$ with *any* number of colours contains a $k$-AP that is either monochromatic (all $k$ terms the same colour) or rainbow (all $k$ terms pairwise different colours) — the *canonical* Ramsey function of Erdős and Graham (P. Erdős, R. L. Graham, *Old and New Problems and Results in Combinatorial Number Theory*, L'Enseignement Mathématique Monographie No. 28, 1980; Erdős Problem #190, erdosproblems.com/190).

Corollary 2.1 (Ji Ho Bae, arXiv:2604.20588, quoted verbatim). *"For every $k\ge2$, $H(k)\ge W(k-1,k)$."*

Proof (quoted verbatim, one line). *"Let $N=W(k-1,k)-1$. There exists a $(k-1)$-colouring $\chi:[N]\to[k-1]$ with no monochromatic $k$-AP. Since $\chi$ uses only $k-1$ colours, no $k$-AP has $k$ distinct colours, so $\chi$ is also rainbow-$k$-AP-free. Thus $\chi$ has neither mono nor rainbow $k$-APs, giving $H(k)>N$ and hence $H(k)\ge W(k-1,k)$."* (arXiv:2604.20588v1, Corollary 2.1 and proof, p.2). Bae notes this reduction "is folklore and is used e.g. in [Butler et al. 2016, §2]" — i.e. it predates and is independent of his paper; his contribution is what is *composed* with it (see Technique below).

Companion fact used in the same framework (surjective/anti-Ramsey side). The anti-van der Waerden number $\mathrm{aw}([n],k)$ = the least $t$ such that every *surjective* $t$-colouring of $[n]$ (using exactly $t$ distinct colours, each at least once) contains a rainbow $k$-AP, satisfies $\mathrm{aw}([n],k)\ge k$ for all $n\ge k$ — "a direct pigeonhole consequence of the definitions, since any surjective $t$-colouring with $t<k$ colours cannot place $k$ distinct colours on any $k$-term AP" (arXiv:2604.20588v1, §2.2; framework due to V. Jungić, J. Licht, M. Mahdian, J. Nešetřil, R. Radoičić, "Rainbow arithmetic progressions and anti-Ramsey results," *Combin. Probab. Comput.* 12(5–6) (2003) 599–620, and systematically studied by S. Butler et al., "Rainbow arithmetic progressions," *J. Combin.* 7 (2016) 595–626).

A second, classical instance (Schur numbers vs. diagonal multicolour Ramsey numbers). The Schur number $S(r)$ (least $N$ such that every $r$-colouring of $[N]$ contains a monochromatic solution to $x+y=z$) satisfies $S(r)\le R_r(3)-2$, where $R_r(3)=R(3,3,\dots,3)$ ($r$ copies) is the $r$-colour diagonal Ramsey number for triangles. Proof idea: given an $r$-colouring $\chi:[1,N]\to[r]$ with no monochromatic Schur triple, colour the edges of $K_{N+1}$ (vertices $0,1,\dots,N$) by $\chi(v-u)$ for $u<v$; a monochromatic triangle on vertices $i>j>k$ gives $x=i-j,\ y=j-k,\ z=i-k=x+y$, a monochromatic Schur triple — contradiction, so $K_{N+1}$ (hence any $K_M$ with $M\ge N+1$) has no monochromatic triangle in this colouring, forcing $R_r(3)>N+1$, i.e. $N\le R_r(3)-2$. Again the reduction is a pure encoding/exhaustion trick (differences-as-edge-colours), not an application of any deep structural theorem — the heavy lifting (bounding $R_r(3)$) is entirely outsourced to Ramsey theory proper.

Facts

- Origin of the H(k)/W(k-1,k) instance. Folklore, used at least as early as S. Butler et al., "Rainbow arithmetic progressions," *J. Combin.* 7 (2016) 595–626, §2; restated and reproved (one line, for completeness) as Corollary 2.1 in Ji Ho Bae, "A resolution of Erdős Problem #190 via Erdős–Lovász, BCT, and Baker–Harman–Pintz," arXiv:2604.20588 (2026), which is the paper that *uses* the reduction to resolve Erdős #190 — canonical Ramsey growth rate H(k)^{1/k}/k → ∞ (SOLVED). - What the reduction alone buys, and what it doesn't. The reduction $H(k)\ge W(k-1,k)$ is completely free — a two-sentence pigeonhole argument — but by itself it only *transfers* whatever lower bound is known for $W(k-1,k)$; it supplies zero new quantitative content. The entire difficulty of resolving Erdős Problem #190 (whether $H(k)^{1/k}/k\to\infty$) lived in proving a strong enough lower bound on $W(r,k)$ at a colour count $r$ that itself grows with $k$ (Bae uses $r_0=\lfloor k/\log k\rfloor$), via the Erdős–Lovász Local-Lemma bound $W(r,k)\gtrsim r^{k-1}/k$ (Lovász Local Lemma (symmetric, general/asymmetric, and algorithmic/random-recoloring variants) — probabilistic existence when bad events are individually non-negligible but sparsely dependent) chained with the Blankenship–Cummings–Taranchuk recurrence $W(r,k)\ge p\,(W(r-1,k)-1)$ for primes $p\le k$ (M. Blankenship, J. Cummings, V. Taranchuk, *European J. Combin.* 69 (2018) 163–168) and a Baker–Harman–Pintz prime-gap bound (*Proc. London Math. Soc.* 83(3) (2001) 532–562) to reach $r=k-1$. See Erdős #190 — canonical Ramsey growth rate H(k)^{1/k}/k → ∞ (SOLVED) for the full assembled proof. - **Composing the reduction at a *fixed* base is provably weak.** Bae's paper (§4.1) notes explicitly that composing the reduction with Berlekamp's 1968 two-colour bound $W(2,k)>(k-1)2^{k-1}$ (E. R. Berlekamp, *Canad. Math. Bull.* 11(3) (1968) 409–414) via the BCT recurrence at a *fixed* base colour count gives only $H(k)^{1/k}/k\to2$ — a bounded ratio, not divergence. Likewise composing with Z. Hunter's 2025 fixed-$r$ multicolour bound $W(r,k)>(a\cdot3^b)^{(1-o_r(1))k}$ (*Israel J. Math.* 267 (2025) 783–795) gives only a conditional $(\log k)^{1/2-o(1)}$-type rate. The pigeonhole reduction itself is colour-count-agnostic — it is equally valid feeding in $W(2,k)$, $W(r,k)$ for fixed $r$, or $W(r_0(k),k)$ for growing $r_0(k)$ — so the reduction's strength as used in a proof is entirely determined by which lower bound on $W(\cdot,k)$ one composes it with. This is the key lesson for reuse: identify whether the colour-count parameter feeding the reduction can be let to *grow with the main parameter*, since that is what separates a bounded-ratio consequence from a divergent one. - **Structural reason the sibling problem Erdős #138 — does W(k)^{1/k} → ∞ for van der Waerden numbers? (fixed 2-colour van der Waerden growth, $W(k)^{1/k}\to\infty$) remains open** while Erdős #190 — canonical Ramsey growth rate H(k)^{1/k}/k → ∞ (SOLVED) is solved: #138's colour count is *fixed at $r=2$ by the problem statement itself*, so the "let the colour count grow" move that powers Bae's use of the reduction is structurally unavailable there — the reduction has nothing analogous to transfer through. - Monotonicity lemma used alongside the reduction. $W(r',k)\ge W(r,k)$ for $r'\ge r$ (any $r$-colouring is trivially an $r'$-colouring using $\le r$ of the $r'$ available colours) — a second, even more elementary pigeonhole-flavoured fact, used in Bae's proof to move from a bound at the prime $p^*\le k-1$ up to the target colour count $k-1$ (arXiv:2604.20588v1, Theorem 2.11). - Second canonical instance: Schur numbers vs. diagonal Ramsey numbers. $S(r)\le R_r(3)-2$ (edges of $K_{N+1}$ coloured by $\chi(v-u)$; a monochromatic triangle's edge-differences give a monochromatic Schur triple). This is the same *shape* of reduction — encode one combinatorial-avoidance problem's colourings as another's, so that a lower/upper bound transfers with zero extra structural work — but the encoding here is a relabelling map (differences $\to$ edge colours) rather than a colour-count counting argument; both are usually filed together as "elementary/folklore reductions" in Ramsey-theory surveys. - Third instance, same family: anti-van der Waerden lower bound $\mathrm{aw}([n],k)\ge k$. A one-line surjectivity pigeonhole (fewer than $k$ colours used $\Rightarrow$ no rainbow $k$-AP possible at all), the direct analogue of the $H(k)\ge W(k-1,k)$ argument but stated for the *anti*-Ramsey (rainbow-forcing) function rather than the canonical (mono-or-rainbow) one; both trace to the same Jungić–Licht–Mahdian–Nešetřil–Radoičić anti-Ramsey framework.

Technique

WHEN it applies. Whenever two Ramsey-type functions $f,g$ are defined by the *same* underlying forbidden/forced-pattern condition but under *different colour-cardinality constraints* (fixed number of colours $r$ vs. unconstrained; fixed $r$ vs. $r-1$; surjective-with-exactly-$t$-colours vs. at-most-$t$-colours; monochromatic-only vs. monochromatic-or-rainbow), and one constraint is *provably a special case, or a strictly weaker consequence, of the other purely by counting how many colours a witness structure of size $k$ can display*. The tell-tale sign: the target pattern (a $k$-AP, a Schur triple, a monochromatic $K_s$, …) has a fixed size $k$, and "rainbow" or "monochromatic" are extremes of the same colour-multiplicity spectrum that a colouring restricted to $<k$ colours (or exactly $1$ colour, or $\ge k$ colours) cannot straddle.

WHY it works (the mechanism). No structural combinatorics is needed at all — only a counting/exhaustion tautology of the form "a $k$-element multiset drawn from a palette of size $<k$ cannot be injective (all-distinct)," or its dual "a $k$-element multiset drawn from a palette of size $1$ cannot be non-constant." This is literally the pigeonhole principle applied to the *colour palette itself*, one level up from its usual application to the coloured objects. Because it needs nothing about the coloured *structure* ($k$-APs, triangles, whatever), the reduction is completely generic: it survives verbatim across every setting where "monochromatic" and "rainbow" (or "$r$-coloured" and "$(r-1)$-coloured") are both meaningful notions for the same underlying $k$-pattern, and it costs nothing to prove — the entire content of any *interesting* theorem built on it lives in bounding the function on the other side of the inequality.

HOW to use it to prove things (recombination steps)

1. Identify a "loose" Ramsey-type function you cannot yet bound directly (here: $H(k)$, the canonical/colour-count-unconstrained function) and a "tight" sibling function with a fixed, specific colour count that is already well studied (here: $W(r,k)$, the ordinary van der Waerden number, extensively bounded via the Lovász Local Lemma, BCT-type recurrences, and explicit constructions). 2. **Find the colour count at which the tight function's extremal colouring is *forced* to also satisfy the loose function's stricter avoidance condition — typically "one less than the pattern size" ($r=k-1$ colours can never realize a rainbow $k$-pattern) or "exactly the pattern size" (surjective $t=k$ colouring can realize but $t<k$ cannot). Write down the one-line witness argument (Corollary 2.1's proof above is the template: take the extremal $(k-1)$-colouring witnessing $W(k-1,k)-1$, observe it is automatically rainbow-free too). 3. Transfer any known or newly-proved lower bound on the tight function at that specific colour count directly into a lower bound on the loose function** — $H(k)\ge W(k-1,k)$ means *every* advance in lower-bounding $W(k-1,k)$ (bigger constructions, better Local-Lemma bounds, better recurrences) is *automatically* an advance in lower-bounding $H(k)$, with no re-proof needed. 4. Check whether the colour-count parameter on the tight side can be decoupled from a fixed constant and let to grow with the main parameter ($r=r(k)\to\infty$, not $r$ fixed). This is the step that determines whether the composed bound is *merely* exponential (fixed $r$, as in the Berlekamp/Hunter comparisons in Facts above) or *super-exponential relative to $k^k$* (growing $r_0(k)=\lfloor k/\log k\rfloor$, as in Bae's resolution of #190) — the pigeonhole reduction step itself is indifferent to this choice, so the choice must be made and optimized separately, typically by writing the composed bound as an explicit function of the free colour-count parameter and optimizing it (Bae §4.2 does exactly this: $R(r_0)=r_0\exp(-r_0\log k/k)$, optimized at $r_0=k/\log k$). 5. Recognize the reduction's dual/mirror forms elsewhere before reinventing it: the same one-line counting argument appears as $\mathrm{aw}([n],k)\ge k$ (anti-Ramsey/surjective side) and, in an encoding rather than counting flavour, as $S(r)\le R_r(3)-2$ (Schur numbers via edge-difference colourings of $K_{N+1}$) and more generally $S(r;k_0,\dots,k_{r-1})\le R_r(k_0,\dots,k_{r-1})-1$ for generalized Schur equations. When facing a new pair of Ramsey-type functions differing only in colour-cardinality constraint or in an encoding of one combinatorial object as another, check first whether a one-line pigeonhole/exhaustion argument already bridges them before searching for a deep proof.

What it does NOT give. The reduction never produces new quantitative content by itself — it is a lossless but zero-information transfer of whatever is already known (or later proved) about the tight-side function. It also gives only a lower bound in the $H(k)\ge W(k-1,k)$ direction (existence of a bad colouring transfers "downward" in colour-count-strictness, i.e. from fewer to more colours available on the loose side); it says nothing about upper bounds on $H(k)$, which (as of the Bae paper) remain completely open and require a structurally different argument (e.g. controlling $\mathrm{aw}([n],k)$ from above).

Related

- Erdős #190 — canonical Ramsey growth rate H(k)^{1/k}/k → ∞ (SOLVED) — Erdős–Graham's canonical-Ramsey growth-rate question $H(k)^{1/k}/k\to\infty$, SOLVED (2026) by Ji Ho Bae (arXiv:2604.20588) via exactly the pigeonhole reduction $H(k)\ge W(k-1,k)$ documented on this page, composed with a growing-colour-count Erdős–Lovász/BCT/Baker–Harman–Pintz chain; the full worked proof and its "what made this composition succeed" analysis live there. - Erdős #138 — does W(k)^{1/k} → ∞ for van der Waerden numbers? — the *fixed*-colour ($r=2$) van der Waerden growth-rate sibling, $W(k)^{1/k}\to\infty$, still open; documents why the same pigeonhole reduction has no analogous lever to pull once the colour count is fixed by the problem statement rather than free to grow. - Lovász Local Lemma (symmetric, general/asymmetric, and algorithmic/random-recoloring variants) — probabilistic existence when bad events are individually non-negligible but sparsely dependent — supplies the $W(r,k)\gtrsim r^{k-1}/k$ existence bound that the reduction on this page transfers into a bound on $H(k)$; the reduction and the Local Lemma bound are logically independent ingredients that are *composed*, not the same technique. - Concepts referenced but not yet their own pages: "van der Waerden's theorem" / `concept/van-der-waerden-theorem (defines $W(r,k)$'s finiteness, the classical fact this whole family of reductions presupposes) and "Schur's theorem" / concept/schur-theorem` (the $x+y=z$ analogue, whose Schur-number-vs-Ramsey-number reduction is this page's second worked instance).