DHJ(2.7) - Revision history

Teorth at 05:29, 24 February 2009

2009-02-24T05:29:32Z

← Older revision		Revision as of 22:29, 23 February 2009
Line 1:		Line 1:
	'''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.)		'''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.)
	~~<p>~~
	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)]].		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>.		'''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>.

Teorth at 05:28, 24 February 2009

2009-02-24T05:28:59Z

← Older revision		Revision as of 22:28, 23 February 2009
Line 1:		Line 1:
	'''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.)		'''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.)
	<p>		<p>
			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>0</math>.		'''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		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

Teorth: alpha is a set, not a number

2009-02-24T05:25:28Z

alpha is a set, not a number

← Older revision		Revision as of 22:25, 23 February 2009
Line 1:		Line 1:
	'''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\~~in {\mathbf N}</math>, <math>\|\alpha\| <\infty~~</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.)		'''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.)
	<p>		<p>
	'''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>.		'''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>.

68.249.221.223 at 03:59, 24 February 2009

2009-02-24T03:59:18Z

← Older revision		Revision as of 20:59, 23 February 2009
Line 6:		Line 6:
	\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>,		\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		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}</math> for ''every'' <math>v\in [3]^r</math>.		<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		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

68.249.221.223 at 02:49, 24 February 2009

2009-02-24T02:49:51Z

← Older revision		Revision as of 19:49, 23 February 2009
Line 1:		Line 1:
	'''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\in {\mathbf N}</math>, <math>\|\alpha\| <\infty</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>		'''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\in {\mathbf N}</math>, <math>\|\alpha\| <\infty</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.)
	<p>		<p>
	'''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>.		'''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>.

68.249.221.223 at 02:07, 24 February 2009

2009-02-24T02:07:18Z

← Older revision		Revision as of 19:07, 23 February 2009
Line 1:		Line 1:
	'''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\in {\mathbf N}</math>, <math>\|\alpha\| <\infty</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>		'''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\in {\mathbf N}</math>, <math>\|\alpha\| <\infty</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>
			<p>
	~~{\bf~~ 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>.		'''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		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(		<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(

68.249.221.223 at 02:02, 24 February 2009

2009-02-24T02:02:25Z

← Older revision		Revision as of 19:02, 23 February 2009
Line 1:		Line 1:
	'''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\in {\mathbf N}</math>, <math>\|\alpha\| ~~???~~ 0</math>.		'''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\in {\mathbf N}</math>, <math>\|\alpha\| <\infty</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>

			{\bf 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		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(		<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(
Line 11:		Line 12:
	:<math>z_1z_2\cdots z_r</math>,		:<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>\{1,j\}</math>, <math>0\leq i<j<r</math>, according to whether or not the sets		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>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,		<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,

Teorth: New page: '''DHJ (2.7)''': For all $\delta>0$ there exists $n=n(\delta)$ such that if $A\subset [3]^n$ with $|A|> \delta 3^n$ , there exists $\alpha\i...$

2009-02-23T22:13:58Z

New page: '''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\i...

New page

'''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\in {\mathbf N}</math>, <math>|\alpha| ??? 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}</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>\{1,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>.