View source for DHJ(2.7)

'''DHJ (2.7)''': For all <math>\delta>0</math> there exists <math>n=n(\delta)</math> such that if <math>A\subset [3]^n</math> with <math>|A|> \delta 3^n</math>, there exists <math>\alpha\subset [n]</math>, and variable words <math> w_{01}, w_{12}, w_{20}</math> such that <math>\{n: w_{xy}=3\} =\alpha, \; xy\in \{01,12,02\},</math> and <math>\big\{w_{xy}(x),w_{xy}(y):xy\in \{01,12,02\}\big\}\subset A.</math> (Remark: <math>w(x)</math> is just <math>w</math> with <math>x</math> substituted for 3.) 

In other words, DHJ(2.7) asserts that in a dense set of <math>[3]^n</math>, one can find three ''parallel'' [[combinatorial line]]s, which intersect the set in the 0 and 1, 1 and 2, and 2 and 0 positions respectively.  This is slightly stronger than [[DHJ(2.6)]] and is implied by [[DHJ(3)]].

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

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

:<math>z_1z_2\cdots z_r</math>,

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