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. 357, Theorem 20 (published scan).

Statement. The orthogonal product of two finite Ramsey configurations is Ramsey. More precisely, if a finite T⊆RN1T\subseteq\mathbb R^{N_1} forces K1K_1 in rr colors and ∣T∣=t|T|=t, and R(K2,N2,rt)R(K_2,N_2,r^t) holds, then R(K1×K2,N1+N2,r)R(K_1\times K_2,N_1+N_2,r) holds.

Complete proof. Fix rr. By compactness, choose a finite witness TT for K1K_1 in rr colors, with t=∣T∣t=|T|. Since K2K_2 is Ramsey, choose N2N_2 and a finite witness S⊆RN2S\subseteq\mathbb R^{N_2} for K2K_2 in rtr^t colors.

Given any rr-coloring cc of T×ST\times S, color y∈Sy\in S by its pattern (c(x,y))x∈T(c(x,y))_{x\in T}. There are at most rtr^t patterns. Thus a copy K2′⊆SK_2'\subseteq S has a constant pattern. Choose y0∈K2′y_0\in K_2' and color x∈Tx\in T by c(x,y0)c(x,y_0). There is a monochromatic copy K1′⊆TK_1'\subseteq T. Constancy of the patterns makes cc constant on K1′×K2′K_1'\times K_2'. Its squared pair distances are sums of the corresponding squared factor distances, so it is congruent to K1×K2K_1\times K_2. Restrict arbitrary colorings of RN1+N2\mathbb R^{N_1+N_2} to this finite product to finish. □\square

Source precision. The last dimension-summary line on p. 357 prints rn1r^{n_1} for the second color count, although the proof uses rtr^t with t=∣T∣t=|T|. Ambient dimension does not bound the number of points in this finite witness. The quantified statement above retains the witness size; it does not infer the printed stronger dimension bound. The proof itself already has the correct pattern count.

For the extension to copies using more than one color, see theorem_28. The stronger exponential-density product theorem is compiled separately in theorem_2_2.

Bears on. #174.