From Polymath1Wiki
Jump to: navigation, search

DHJ (2.7): For all [math]\delta\gt0[/math] there exists [math]n=n(\delta)[/math] such that if [math]A\subset [3]^n[/math] with [math]|A|\gt \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 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 [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\gt0[/math]. Let [math]m\gt{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|\gt\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|\gt (\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| \gt {\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\ltj\ltr[/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\ltk_2\lt\cdots \ltk_m\ltr[/math] such that [math]\big\{\{ k_i,k_j\}: 0\leq i\ltj\ltm \big\}[/math] is monochromatic for this coloring. By pigeonhole, for, say, [math]xy=10[/math], there are [math]i\ltj[/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\ltk_1[/math], [math]s_i=3[/math], [math]k_1\leq i\ltk_2[/math], and [math]s_i=y[/math], [math]k_2\leq i\ltr[/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\lt\delta_0[/math].