Wiki
Wiki

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

Updated


Source. Published pp. 215–217, 220–221 and 231: Definition 1.1 on p. 215, Definition 1.2 and the circumradius on p. 216, Definitions 1.4 and 1.5 on p. 217, Definition 3.1 on pp. 220–221, the product on p. 221 and Definition 3.11 on p. 231. (canonical PDF).

Write S(R,m)={x∈Rm:∥x∥=R}S(R,m)=\{x\in\mathbb R^m:\|x\|=R\}; mm is the ambient dimension. The paper defines the circumradius ρ(X)\rho(X) of a spherical set as "the radius of the smallest sphere containing XX" (p. 216), a sphere on which XX lies. That sphere is the one whose center lies in aff⁡X\operatorname{aff}X (circumradius_continuity); it is not the radius of a smallest enclosing ball.

Definition 1.1. X⊆RdX\subseteq\mathbb R^d is Ramsey if for every χ≥2\chi\ge2 there is an integer n=n(X,χ)n=n(X,\chi) such that every χ\chi-colouring of Rn\mathbb R^n has a monochromatic subset congruent to XX.

Definition 1.2. X⊆RdX\subseteq\mathbb R^d is sphere Ramsey if for every χ≥2\chi\ge2 there are an integer n=n(X,χ)n=n(X,\chi) and a real ϱ=ϱ(X,χ)>0\varrho=\varrho(X,\chi)>0 such that every χ\chi-colouring of S(ϱ,n)S(\varrho,n) has a monochromatic subset of that sphere congruent to XX.

Definition 1.4. X⊆RdX\subseteq\mathbb R^d is exponentially Ramsey if there is a real σ=σ(X)>0\sigma=\sigma(X)>0 such that for every integer n≥dn\ge d and every χ\chi-colouring of Rn\mathbb R^n with χ≤(1+σ)n\chi\le(1+\sigma)^n some monochromatic subset is congruent to XX.

Definition 1.5. X⊆RdX\subseteq\mathbb R^d with ρ(X)=ρ\rho(X)=\rho is strong Ramsey if for every real δ>0\delta>0 there is a real σ=σ(X)>0\sigma=\sigma(X)>0 such that for every integer n≥dn\ge d and every χ\chi-colouring of S(ρ+δ,n)S(\rho+\delta,n) with χ≤(1+σ)n\chi\le(1+\sigma)^n some monochromatic subset of that sphere is congruent to XX. The eventual reading used in this compilation, for all sufficiently large nn with σ\sigma depending on XX and δ\delta, is explained under Source precision.

Definition 3.1. For a real α>0\alpha>0, X⊆RdX\subseteq\mathbb R^d with ρ(X)=ρ\rho(X)=\rho is α\alpha-hyper Ramsey if there are reals c=c(X,α)c=c(X,\alpha) and ϵ=ϵ(X,α)>0\epsilon=\epsilon(X,\alpha)>0 and an integer m0=m0(α)m_0=m_0(\alpha) such that every m≥m0m\ge m_0 has a finite subset H(m)⊆Rm\mathcal H(m)\subseteq\mathbb R^m with

(i) H(m)⊆S(ρ2+α,m),(ii) ∣H(m)∣<cm,\text{(i) }\mathcal H(m)\subseteq S(\sqrt{\rho^2+\alpha},m),\qquad \text{(ii) }|\mathcal H(m)|<c^m,

and (iii) every K⊆H(m)\mathcal K\subseteq\mathcal H(m) with ∣K∣≥(1−ϵ)m∣H(m)∣|\mathcal K|\ge(1-\epsilon)^m|\mathcal H(m)| contains a subset congruent to XX. It is hyper Ramsey if it is α\alpha-hyper Ramsey for every real α>0\alpha>0. Since (iii) applied to K=H(m)\mathcal K=\mathcal H(m) forces H(m)\mathcal H(m) to be nonempty, (ii) needs c>1c>1; the pages of this card take c>1c>1 and 0<ϵ<10<\epsilon<1, which loses nothing. Equivalently, every XX-free subset of H(m)\mathcal H(m) has relative size strictly less than (1−ϵ)m(1-\epsilon)^m. The printed m0=m0(α)m_0=m_0(\alpha) is read as also depending on XX.

Product (p. 221). For X⊆RnX\subseteq\mathbb R^n and Y⊆RmY\subseteq\mathbb R^m, X∗Y={x∗y:x∈X, y∈Y}X*Y=\{x*y:x\in X,\ y\in Y\}, where x∗yx*y is the concatenation (x1,…,xn,y1,…,ym)(x_1,\ldots,x_n,y_1,\ldots,y_m).

Definition 3.11. For reals 1≥μ≥01\ge\mu\ge0 and β>0\beta>0, a simplex T={t1,…,td+1}T=\{t_1,\ldots,t_{d+1}\} is (μ,β)(\mu,\beta)-regular if β(1−μ)≤∥ti−tj∥2≤β(1+μ)\beta(1-\mu)\le\|t_i-t_j\|^2\le\beta(1+\mu) for every 1≤i<j≤d+11\le i<j\le d+1. Thus β\beta has the units of a squared length.

The elementary transfers below will be used with their exact radii.

Proof.

A singleton is hyper-Ramsey: in each dimension use one point on the specified sphere, any c>1c>1 and any 0<ϵ<10<\epsilon<1. A subset of this witness meeting the positive density threshold is nonempty.

If witnesses on a fixed sphere S(R,m)S(R,m) are moved by

x⟼(x,R′2−R2)∈Rm+1,R′≥R,x\longmapsto (x,\sqrt{R'^2-R^2})\in\mathbb R^{m+1},\qquad R'\ge R,

they lie exactly on S(R′,m+1)S(R',m+1), with all distances and cardinalities unchanged. If their avoiding density was less than (1−ϵ)m(1-\epsilon)^m, put 1−ϵ′=1−ϵ1-\epsilon'=\sqrt{1-\epsilon}. For N=m+1≥2N=m+1\ge2,

(1−ϵ)m≤(1−ϵ)N/2=(1−ϵ′)N.(1-\epsilon)^m\le(1-\epsilon)^{N/2}=(1-\epsilon')^N.

This proves radius enlargement in every sufficiently large dimension, including the equality case R′=RR'=R. Zero-coordinate padding alone preserves a fixed radius and distances. Scaling all coordinates by t>0t>0 changes ρ\rho to tρt\rho and squared slack α\alpha to t2αt^2\alpha.

If a witness forces BB, it also forces any nonempty A⊆BA\subseteq B on that same sphere. The squared slack for AA is then R2−ρ(A)2R^2-\rho(A)^2, not the squared slack originally assigned to BB. In particular, this does not prove that AA is hyper-Ramsey at every arbitrarily small slack above its own intrinsic radius.

Hyper-Ramsey implies strong Ramsey. Given δ>0\delta>0, take α=(ρ+δ)2−ρ2>0\alpha=(\rho+\delta)^2-\rho^2>0 and the corresponding witnesses. If q≤(1−ϵ)−mq\le(1-\epsilon)^{-m}, one color class has density at least 1/q≥(1−ϵ)m1/q\ge(1-\epsilon)^m, including equality, and contains XX. Thus one may take 1+σ=(1−ϵ)−11+\sigma=(1-\epsilon)^{-1} in the eventual assertion.

For completeness, an eventual strong assertion can be extended to every m≥d+1m\ge d+1, where d=dim⁡aff⁡Xd=\dim\operatorname{aff}X, by decreasing σ\sigma: choose it so that (1+σ)m<2(1+\sigma)^m<2 in the finitely many earlier dimensions. Only the one-color case then remains, and XX fits on every sphere of radius ρ+δ\rho+\delta in those dimensions by the one-coordinate lift. If only q≥2q\ge2 is quantified, the source's lower bound m≥dm\ge d can be used instead, since the exceptional initial dimensions are vacuous.

Source precision.

Definition 1.5 prints σ=σ(X)\sigma=\sigma(X) after quantifying δ\delta; the proof supplies dependence on δ\delta as well. Its all-m≥dm\ge d wording must be read with the earlier q≥2q\ge2 convention: a full dd-simplex cannot be placed on a strictly larger sphere in Rd\mathbb R^d even with one color. The eventual formulation above and the explicit m≥d+1m\ge d+1 extension remove this ambiguity. The distinction between a containing sphere and an enclosing ball is essential.

Dependencies. The intrinsic-radius facts are proved in circumradius_continuity.

Bears on. #174.