DHJ(2.7)

DHJ (2.7): For all [math]\displaystyle{ \delta\gt 0 }[/math] there exists [math]\displaystyle{ n=n(\delta) }[/math] such that if [math]\displaystyle{ A\subset [3]^n }[/math] with [math]\displaystyle{ |A|\gt \delta 3^n }[/math], there exists [math]\displaystyle{ \alpha\in {\mathbf N} }[/math], [math]\displaystyle{ |\alpha| \lt \infty }[/math], and variable words [math]\displaystyle{ w_{01}, w_{12}, w_{20} }[/math] such that [math]\displaystyle{ \{n: w_{xy}=3\} =\alpha, \; xy\in \{01,12,02\}, }[/math] and [math]\displaystyle{ \big\{w_{xy}(x),w_{xy}(y):xy\in \{01,12,02\}\big\}\subset A. }[/math]

{\bf Proof.} Let [math]\displaystyle{ \delta_0 }[/math] be the infimum of the set of [math]\displaystyle{ \delta }[/math] for which the conclusion holds and assume for contradiction that [math]\displaystyle{ \delta_0\gt 0 }[/math]. Let [math]\displaystyle{ m\gt {3\over \delta_0} }[/math] and choose by Ramsey’s theorem an [math]\displaystyle{ r }[/math] such that for any 8-coloring of the 2-subsets of [math]\displaystyle{ [r] }[/math], there is an [math]\displaystyle{ m }[/math]-subset [math]\displaystyle{ B\subset [r] }[/math] all of whose 2-subsets have the same color. Let [math]\displaystyle{ \delta=\delta_0-{\delta_0\over 4\cdot 3^r} }[/math] and put [math]\displaystyle{ n_1=n( \delta_0+{\delta_0\over 4\cdot 3^r}) }[/math]. Finally put [math]\displaystyle{ n=r+n_1 }[/math] and suppose [math]\displaystyle{ A\subset [3]^n }[/math] with [math]\displaystyle{ |A|\gt \delta 3^n }[/math]. For each [math]\displaystyle{ v\in [3]^r }[/math], let [math]\displaystyle{ E_v=\{w\in [3]^{n_1}:vw\in A\} }[/math]. If [math]\displaystyle{ |E_v|\gt (\delta_0+{\delta_0\over 4\cdot 3^r})3^{n_1} }[/math] for some [math]\displaystyle{ v }[/math] we are done; otherwise [math]\displaystyle{ |E_v| \gt {\delta_0\over 3} }[/math] for every [math]\displaystyle{ v\in [3]^r }[/math].

Some notation: for [math]\displaystyle{ i\in [r] }[/math] and [math]\displaystyle{ xy\in \{10,21,02\} }[/math], let [math]\displaystyle{ v_i^{xy}\in [3]^r }[/math] be the word

[math]\displaystyle{ z_1z_2\cdots z_r }[/math],

where [math]\displaystyle{ z_a=x }[/math] if [math]\displaystyle{ 0\leq a\leq i }[/math] and [math]\displaystyle{ z_a=y }[/math] otherwise. Color [math]\displaystyle{ \{i,j\} }[/math], [math]\displaystyle{ 0\leq i\lt j\lt r }[/math], according to whether or not the sets [math]\displaystyle{ E_{v_i^{xy}}\cap E_{v_j^{xy}} }[/math] are empty or not, [math]\displaystyle{ xy\in \{10,21,02\} }[/math]. (This is an 8-coloring.) By choice of [math]\displaystyle{ r }[/math] we can find [math]\displaystyle{ 0\leq k_1\lt k_2\lt \cdots \lt k_m\lt r }[/math] such that [math]\displaystyle{ \big\{\{ k_i,k_j\}: 0\leq i\lt j\lt m \big\} }[/math] is monochromatic for this coloring. By pigeonhole, for, say, [math]\displaystyle{ xy=10 }[/math], there are [math]\displaystyle{ i\lt j }[/math] such that [math]\displaystyle{ E_{v_{k_i}^{xy}}\cap E_{v_{k_j}^{xy}}\neq \emptyset }[/math], hence non-empty for all [math]\displaystyle{ i,j }[/math] by monochromicity and similarly for [math]\displaystyle{ xy=21,02 }[/math]. Now for [math]\displaystyle{ xy=10,21,02 }[/math], pick [math]\displaystyle{ u_{xy}\in E_{v_{k_1}^{xy}}\cap E_{v_{k_2}^{xy}} }[/math] and put [math]\displaystyle{ q_{xy}=s_1s_2\cdots s_r }[/math], where [math]\displaystyle{ s_i=x }[/math], [math]\displaystyle{ 0\leq i\lt k_1 }[/math], [math]\displaystyle{ s_i=3 }[/math], [math]\displaystyle{ k_1\leq i\lt k_2 }[/math], and [math]\displaystyle{ s_i=y }[/math], [math]\displaystyle{ k_2\leq i\lt r }[/math]. Finally put [math]\displaystyle{ w_{xy}=q_{xy}u_{xy} }[/math]. Then [math]\displaystyle{ w_{xy}(x)=v^{xy}_{k_2} u_{xy} }[/math] and [math]\displaystyle{ w_{xy}(y)=v^{xy}_{k_1} u_{xy} }[/math] are in [math]\displaystyle{ A }[/math], [math]\displaystyle{ xy\in \{10,21,02\} }[/math]. Hence [math]\displaystyle{ n=n(\delta) }[/math], contradicting [math]\displaystyle{ \delta\lt \delta_0 }[/math].