# DHJ(2.7)

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

In other words, DHJ(2.7) asserts that in a dense set of $[3]^n$, one can find three parallel combinatorial lines, 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 $\delta_0$ be the infimum of the set of $\delta$ for which the conclusion holds and assume for contradiction that $\delta_0\gt0$. Let $m\gt{3\over \delta_0}$ and choose by Ramsey’s theorem an $r$ such that for any 8-coloring of the 2-subsets of $[r]$, there is an $m$-subset $B\subset [r]$ all of whose 2-subsets have the same color. Let $\delta=\delta_0-{\delta_0\over 4\cdot 3^r}$ and put $n_1=n( \delta_0+{\delta_0\over 4\cdot 3^r})$. Finally put $n=r+n_1$ and suppose $A\subset [3]^n$ with $|A|\gt\delta 3^n$. For each $v\in [3]^r$, let $E_v=\{w\in [3]^{n_1}:vw\in A\}$. If $|E_v|\gt (\delta_0+{\delta_0\over 4\cdot 3^r})3^{n_1}$ for some $v$ we are done; otherwise $|E_v| \gt {\delta_0\over 3}3^{n_1}$ for every $v\in [3]^r$.

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

$z_1z_2\cdots z_r$,

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