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. 221–223, Lemma 3.4 and its proof. (canonical PDF).

If V⊆Rd1V\subseteq\mathbb R^{d_1} is a finite αV\alpha_V-hyper-Ramsey set and T⊆Rd2T\subseteq\mathbb R^{d_2} is a finite αT\alpha_T-hyper-Ramsey set, then the product V∗T⊆Rd1+d2V*T\subseteq\mathbb R^{d_1+d_2} is (αV+αT)(\alpha_V+\alpha_T)-hyper-Ramsey (Lemma 3.4, p. 221). Both slacks are positive, as Definition 3.1 requires.

Proof.

The intrinsic product radius satisfies ρ(V∗T)2=ρ(V)2+ρ(T)2\rho(V*T)^2=\rho(V)^2+\rho(T)^2 by circumradius_continuity. If either factor is a singleton, the product is congruent to the other factor. Radius enlargement in definitions adds the singleton's positive squared slack and proves the assertion. Hence assume t=∣T∣≥2t=|T|\ge2 and both factors have at least two points.

Take witnesses HV(n),HT(m)H_V(n),H_T(m) with cardinality bases cV,cT>1c_V,c_T>1 and avoiding density bases aV=1−ϵVa_V=1-\epsilon_V, aT=1−ϵTa_T=1-\epsilon_T in (0,1)(0,1). Choose

τ=−log⁡aV2(t−1)log⁡cT>0,m=⌊τn⌋,Nn=n+m.\tau=\frac{-\log a_V}{2(t-1)\log c_T}>0, \qquad m=\lfloor\tau n\rfloor, \qquad N_n=n+m.

For all large nn, both witnesses exist. Their product HH lies on the sphere of squared radius ρ(V)2+αV+ρ(T)2+αT\rho(V)^2+\alpha_V+\rho(T)^2+\alpha_T and has cardinality less than max⁡(cV,cT)Nn\max(c_V,c_T)^{N_n}.

Let W⊆HW\subseteq H contain no copy of V∗TV*T. For each v∈HV(n)v\in H_V(n), let Wv={t′∈HT(m):(v,t′)∈W}W_v=\{t'\in H_T(m):(v,t')\in W\}. If WvW_v contains bvb_v distinct copies of TT, delete one point from each of those copies. The remaining set is TT-free and has size at least ∣Wv∣−bv|W_v|-b_v. The witness property therefore gives

bv>∣Wv∣−aTm∣HT(m)∣.b_v>|W_v|-a_T^m|H_T(m)|.

This argument counts all copies; it does not require them to be disjoint. Summing over fibers gives, for B=∑vbvB=\sum_vb_v,

B>∣W∣−aTm∣HV(n)∣ ∣HT(m)∣.B>|W|-a_T^m|H_V(n)|\,|H_T(m)|.

For every fixed copy T′⊆HT(m)T'\subseteq H_T(m), the set of vv with {v}∗T′⊆W\{v\}*T'\subseteq W is VV-free. There is at least one such candidate copy in HT(m)H_T(m), since the full witness contains TT. Consequently

B<(∣HT(m)∣t) aVn∣HV(n)∣≤∣HT(m)∣t−1 aVn∣H∣<cTm(t−1)aVn∣H∣≤aVn/2∣H∣.\begin{aligned} B&<\binom{|H_T(m)|}{t}\,a_V^n|H_V(n)|\\ &\le |H_T(m)|^{t-1}\,a_V^n|H|\\ &<c_T^{m(t-1)}a_V^n|H| \le a_V^{n/2}|H|. \end{aligned}

The last inequality uses m≤τnm\le\tau n and the definition of τ\tau. Combining the two counts yields

∣W∣∣H∣<aVn/2+aT⌊τn⌋.\frac{|W|}{|H|}<a_V^{n/2}+a_T^{\lfloor\tau n\rfloor}.

For large nn, ⌊τn⌋≥τn/2\lfloor\tau n\rfloor\ge\tau n/2. Hence the right side is at most 2e−hn2e^{-hn}, where

h=min⁡{−12log⁡aV,−τ2log⁡aT}>0.h=\min\{-\tfrac12\log a_V,-\tfrac\tau2\log a_T\}>0.

Since Nn≤(1+τ)nN_n\le(1+\tau)n, it is at most e−hNn/[2(1+τ)]e^{-hN_n/[2(1+\tau)]} for all sufficiently large nn. This is the required exponential avoiding-density bound on the sequence NnN_n. Its successive gaps are at most 1+⌈τ⌉1+\lceil\tau\rceil. Apply the bounded-gap form of fact_3_10 to obtain witnesses in every large ambient dimension on exactly the same sphere. Its squared slack above the intrinsic product radius is exactly αV+αT\alpha_V+\alpha_T.

Source precision.

The source's displayed construction covers the dimensions n+⌊τn⌋n+\lfloor\tau n\rfloor; it does not by itself cover every large integer. The bounded-gap step supplies that implication. The source equation for τ\tau has an exponent ∣T∣−1|T|-1, so singleton factors were separated before using it. No subset-inheritance assertion at a smaller intrinsic radius enters this proof.

Bears on. #174.