Wiki
Wiki

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

Updated


Source. These are elementary consequences of the definitions on Kříž's published p. 901, used implicitly in the conclusions of Theorems 3.3 and 4.1 (publisher PDF). This page expands those deductions; it is not a separately numbered source theorem.

Statement

Let FF be a finite configuration with equivalence relation EE.

  1. The equality relation is always Ramsey on FF.
  2. If E′⊆EE'\subseteq E and FF is EE-Ramsey, then FF is E′E'-Ramsey.
  3. If FF is EE-Ramsey, every subset A⊆FA\subseteq F is Ramsey for E∩(A×A)E\cap(A\times A).
  4. Congruent configurations have the same Ramsey properties, with their equivalence relations transported by the congruence.
  5. If λ>0\lambda>0, then FF is EE-Ramsey if and only if λF\lambda F is λE\lambda E-Ramsey, where λE={(λx,λy):xEy}\lambda E=\{(\lambda x,\lambda y):xEy\}.

In particular, a subset of a Ramsey configuration is Ramsey. A configuration that is EE-Ramsey with at most ss equivalence classes is ss-Ramsey.

Full proof

For the equality relation, embed FF in any Euclidean space of sufficient dimension. The condition on equal points holds for every coloring. If E′⊆EE'\subseteq E, an embedding whose colors are constant on every EE-class also satisfies all the E′E'-equalities. Restricting the same embedding to AA proves the subset assertion. Composing with a fixed congruence proves invariance under congruence.

For scaling, suppose first that FF is EE-Ramsey and fix kk. Choose a dimension NN that witnesses this property. Given c:RN→[k]c:\mathbb R^N\to[k], apply the property of FF to cλ(v)=c(λv)c_\lambda(v)=c(\lambda v). If ϕ:F→RN\phi:F\to\mathbb R^N is the resulting isometrical embedding, define

ψ(λx)=λϕ(x)(x∈F).\psi(\lambda x)=\lambda\phi(x)\qquad(x\in F).

This is an isometrical embedding of λF\lambda F, because both domain and image distances are multiplied by λ\lambda. For xEyxEy, its two colors are cλ(ϕ(x))c_\lambda(\phi(x)) and cλ(ϕ(y))c_\lambda(\phi(y)), which agree. Thus λF\lambda F is λE\lambda E-Ramsey. Apply the same argument with 1/λ1/\lambda for the converse.

Finally, if each of at most ss classes is monochromatic, their union uses at most ss colors. No condition that distinct classes have distinct colors is needed. □\square

Uses. Theorem 3.3, Theorem 4.1, and the subconfiguration consequence of Theorem 4.3.

Bears on. Problem 174.