A cute proof of Rainbow Ramsey Theorem

Just saw this cute little proof of the Rainbow Ramsey Theorem (an Anti-Ramsey-type Theorem). But before that, a colouring χ:[ω]k→ω\chi:[\omega]^{k}\to\omega is called nn-bounded if |χ−1(c)|≤n|\chi^{-1}(c)|\leq n for all colours c∈ωc\in\omega. We say a set H∈[ω]ωH\in[\omega]^{\omega} is rainbow if χ|[H]k\chi|_{[H]^k} is an injection.

Rainbow Ramsey Theorem (𝖱𝖱𝖳nk\textsf{RRT}^k_n). Let k,n∈ωk,n\in\omega with n≥1n\geq 1, for any nn-bounded colouring χ:[ω]k→ω\chi:[\omega]^{k}\to\omega, there exists a set HH which is rainbow under χ\chi.

Proof. It’s a simple special case of the much general Canonical RT (∞\infty-version), but here is a sweet little application of Infinitary RT. Let ≺\prec be a well-ordering on [ω]k[\omega]^k. Consider the colouring COL:[ω]k→nCOL:[\omega]^{k}\to n defined by COL(x):=|{y∈[ω]k:,y≺x and χ(y)=χ(x)}|.COL(x):=|\{y\in[\omega]^k:, y\prec x\text{ and } \chi(y)=\chi(x)\}|.
By 𝖨𝖱𝖳\textsf{IRT}, ∃H∈[ω]ω\exists H\in[\omega]^{\omega} homogeneous under COLCOL. But notice that for distinct x,y∈[H]kx, y\in[H]^{k}, COL(x)=COL(y)COL(x)=COL(y) and either x≺yx\prec y or y≺xy\prec x forces χ(x)≠χ(y)\chi(x)\neq \chi(y) (FTSOC assume χ(x)=χ(y)\chi(x)=\chi(y), then x≺y⟹COL(y)>COL(x)x\prec y\implies COL(y)>COL(x) and y≺x⟹COL(x)>COL(y)y\prec x\implies COL(x)>COL(y), ⇒⇐\Rightarrow\Leftarrow). From this it follows that HH is rainbow under χ\chi.


Leave a Reply