Wiki
Wiki

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

Updated


Source. Frankl–Rödl, published pp. 1–2 and 6, Definitions 1.1, 2.1, 6.1 and 6.3. All configurations below are finite and nonempty. A brick means its vertex set, with perpendicular edges. A congruent copy preserves every pairwise distance, including reflections.

A subset BB of Rd\mathbb R^d is Ramsey (Definition 1.1, p. 1) if for every r≥2r\ge2 there is some n=n(r,B)n=n(r,B) such that whenever Rn\mathbb R^n is split into rr classes V1∪⋯∪VrV_1\cup\cdots\cup V_r, some class VjV_j contains a congruent copy of BB.

A set A⊂RdA\subset\mathbb R^d is super-Ramsey (Definition 2.1, p. 2) if there are positive constants cc and ϵ\epsilon and, for every n>n0(A)n>n_0(A), a set Xn⊂RnX_n\subset\mathbb R^n with

∣Xn∣<cn,∣Y∣<∣Xn∣(1+ϵ)nwhenever Y⊆Xn contains no congruent copy of A.|X_n|<c^n,\qquad |Y|<\frac{|X_n|}{(1+\epsilon)^n} \quad\text{whenever }Y\subseteq X_n\text{ contains no congruent copy of }A.

Taking YY empty in the second condition shows XnX_n is nonempty, so 1≤∣Xn∣<cn1\le|X_n|<c^n forces c>1c>1 and XnX_n finite. These are finite density witnesses, a stronger requirement than a statement about colorings alone. Constants may depend on the entire configuration.

Elementary deductions. A singleton is super-Ramsey: use a singleton witness in every dimension, since its only avoiding subset is empty. Every nonempty subset A′⊆AA'\subseteq A of a super-Ramsey configuration is super-Ramsey using the same witnesses: an A′A'-free set is AA-free. Similarity preserves the property by scaling each witness by the same positive factor; Euclidean motions do not affect the distances. An isometric realization in another ambient dimension describes the same finite configuration. This last assertion follows by translating one point to zero, recovering the Gram matrix from the pairwise distances, and identifying the two spans isometrically.

If witnesses have been constructed only in dimensions pHpH, where HH is fixed, with avoiding density less than apHa^{pH} for a fixed 0<a<10<a<1, they suffice. For large NN, take p=⌊N/H⌋p=\lfloor N/H\rfloor and append zero coordinates. Then pH≥N/2pH\ge N/2, so apH≤(a)Na^{pH}\le(\sqrt a)^N. The same exponential cardinality bound holds after increasing its base above one if needed. This supplies witnesses for every sufficiently large NN; the configuration itself must remain congruent as pp varies.

For a finite spherical configuration AA, its circumradius ρ(A)\rho(A) is the radius of its smallest containing sphere. Equivalently, project a center of any containing sphere orthogonally onto aff⁡A\operatorname{aff}A; the projected center is equidistant from all points, is unique in that affine span, and minimizes the radius by Pythagoras. A singleton has radius zero. We write S(R,n)={x∈Rn:∥x∥=R}S(R,n)=\{x\in\mathbb R^n:\|x\|=R\}: nn is the ambient dimension, not the dimension of the sphere as a manifold.

The set AA is sphere Ramsey (Definition 6.1, p. 6, after Graham) if for every r≥2r\ge2 there are some n=n(A,r)n=n(A,r) and a positive real R=R(A,r)R=R(A,r) for which every rr-coloring of S(R,n)S(R,n) contains a monochromatic congruent copy of AA. A spherical set AA is hyper-Ramsey (Definition 6.3, p. 6) if for every δ>0\delta>0 the super-Ramsey witnesses of Definition 2.1 can be chosen on S(ρ(A)+δ,n)S(\rho(A)+\delta,n) for n>n0(δ)n>n_0(\delta), with c=c(A,δ)c=c(A,\delta) and ϵ=ϵ(A,δ)\epsilon=\epsilon(A,\delta).

Hyper-Ramsey implies super-Ramsey by fixing any positive δ\delta, and implies sphere Ramsey by taking a witness whose density threshold is below 1/r1/r. Similarity preserves hyper-Ramsey by changing the radius slack accordingly. For a singleton one may take one point on the requested sphere. Unlike ordinary subset closure, the hyper-Ramsey definition changes its target radius when a subset has smaller circumradius; see corollary_6_5.

Proof scope. The elementary deductions and dimension extension above are complete. The definitions do not assert that every spherical set is Ramsey.

Bears on. #174.