Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Source. Published p. 362, Theorem 28 (published scan).

Statement. If each finite configuration KiK_i is ℓi\ell_i-Ramsey, then K1×⋯×KtK_1\times\cdots\times K_t is ℓ1⋯ℓt\ell_1\cdots\ell_t-Ramsey. Products use mutually orthogonal coordinate spaces. The theorem is about the number of colors used by a forced copy, not a fixed number of available colors.

Complete proof. It suffices to treat two factors and iterate. Fix the available number of colors rr. By compactness, choose a finite witness A2A_2 such that every r∣K1∣r^{|K_1|}-coloring of A2A_2 contains a copy of K2K_2 using at most ℓ2\ell_2 colors. Then choose a finite witness A1A_1 such that every r∣A2∣r^{|A_2|}-coloring of A1A_1 contains a copy of K1K_1 using at most ℓ1\ell_1 colors. This order avoids any circular dependence of the witnesses.

An rr-coloring cc of the orthogonal product A1×A2A_1\times A_2 gives each x∈A1x\in A_1 its row vector (c(x,y))y∈A2(c(x,y))_{y\in A_2}. There are at most r∣A2∣r^{|A_2|} row types. Choose a congruent K1′⊆A1K_1'\subseteq A_1 with at most ℓ1\ell_1 row types. Next color each y∈A2y\in A_2 by its column restricted to K1′K_1', namely (c(x,y))x∈K1′(c(x,y))_{x\in K_1'}. There are at most r∣K1∣r^{|K_1|} possible columns, so choose a congruent K2′⊆A2K_2'\subseteq A_2 with at most ℓ2\ell_2 column types.

On K1′×K2′K_1'\times K_2', points in the same row type and column type have the same original color: moving within a row type preserves the entry at any fixed column, and moving within a column type preserves the entry at any fixed row. Thus there are at most ℓ1ℓ2\ell_1\ell_2 original colors. Pairwise squared distances add between orthogonal factors, so this is the required congruent product copy. Embed the finite witness product into a sufficiently large Euclidean space, restrict arbitrary ambient colorings to it, and iterate the two-factor argument. □\square

The source leaves infinite-factor extensions as a separate historical question; no such extension is proved here.

Bears on. #174.