A general partitioning principle - Revision history

Ryanworldwide at 19:18, 16 April 2009

2009-04-16T19:18:02Z

← Older revision		Revision as of 12:18, 16 April 2009
Line 39:		Line 39:
	Now <math>\mathcal{B}_1=\bigcap_{y\in S_1}\mathcal{A}_y.</math> Therefore, since <math>\mathbf{K}</math> is hereditary and a sigma-algebra property, <math>\mathcal{B}_1\in\mathbf{K}.</math> And then, using the sigma-algebra assumption again, we have that <math>\mathcal{A}_{1,y}=\mathcal{A}_y\setminus\mathcal{B}_1\in\mathbf{K}.</math>		Now <math>\mathcal{B}_1=\bigcap_{y\in S_1}\mathcal{A}_y.</math> Therefore, since <math>\mathbf{K}</math> is hereditary and a sigma-algebra property, <math>\mathcal{B}_1\in\mathbf{K}.</math> And then, using the sigma-algebra assumption again, we have that <math>\mathcal{A}_{1,y}=\mathcal{A}_y\setminus\mathcal{B}_1\in\mathbf{K}.</math>

	For every y such that <math>\mathcal{A}_{1,y}</math> has density at least <math>\delta/2</math> in <math>S_y,</math> we return to the first iteration. For this to work, we need n-M to be large enough for the conclusion of the richness hypothesis to be satisfied. For every y such that <math>\mathcal{A}_y</math> has density <em>less</em> than <math>\delta/2</math> we put <math>\mathcal{A}_{1,y}</math> into the "error set" <math>\mathcal{A}''.</math>		For every y such that <math>\mathcal{A}_{1,y}</math> has density at least <math>\delta/2</math> in <math>S_y,</math> we return to the first iteration. For this to work, we need n-M to be large enough for the conclusion of the richness hypothesis to be satisfied. For every y such that <math>\mathcal{A}_{1,y}</math> has density <em>less</em> than <math>\delta/2</math> we put <math>\mathcal{A}_{1,y}</math> into the "error set" <math>\mathcal{A}''.</math>

	===How does the iteration finish?===		===How does the iteration finish?===

Ryanworldwide: Corrected some bugs

2009-04-16T19:17:37Z

Corrected some bugs

← Older revision		Revision as of 12:17, 16 April 2009
Line 35:		Line 35:
	===Second step of the iteration===		===Second step of the iteration===

	Since <math>\mathbf{K}</math> is a hereditary property, the intersection <math>\mathcal{A}_y</math> of <math>\mathcal{A}</math> with <math>S_y</math> belongs to <math>\mathbf{K}</math> for every <math>y\in[k]^{~~[n]\setminus~~ Z}.</math> If <math>y\notin S_1,</math> then no points have been removed from <math>\mathcal{A}_y,</math> so <math>\mathcal{A}_{1,y}=\mathcal{A}_y.</math> If <math>y\in S_1,</math> then <math>\mathcal{A}_{1,y}=\mathcal{A}_y\setminus\mathcal{B}_1.</math>		Since <math>\mathbf{K}</math> is a hereditary property, the intersection <math>\mathcal{A}_y</math> of <math>\mathcal{A}</math> with <math>S_y</math> belongs to <math>\mathbf{K}</math> for every <math>y\in[k]^{Z}.</math> If <math>y\notin S_1,</math> then no points have been removed from <math>\mathcal{A}_y,</math> so <math>\mathcal{A}_{1,y}=\mathcal{A}_y.</math> If <math>y\in S_1,</math> then <math>\mathcal{A}_{1,y}=\mathcal{A}_y\setminus\mathcal{B}_1.</math>

	Now <math>\mathcal{B}_1=\bigcap_{y\in S_1}\mathcal{A}_y.</math> Therefore, since <math>\mathbf{K}</math> is hereditary and a sigma-algebra property, <math>\mathcal{B}_1\in\mathbf{K}.</math> And then, using the sigma-algebra assumption again, we have that <math>\mathcal{A}_{1,y}=\mathcal{A}_y\setminus\mathcal{B}_1\in\mathbf{K}.</math>		Now <math>\mathcal{B}_1=\bigcap_{y\in S_1}\mathcal{A}_y.</math> Therefore, since <math>\mathbf{K}</math> is hereditary and a sigma-algebra property, <math>\mathcal{B}_1\in\mathbf{K}.</math> And then, using the sigma-algebra assumption again, we have that <math>\mathcal{A}_{1,y}=\mathcal{A}_y\setminus\mathcal{B}_1\in\mathbf{K}.</math>

	For every y such that <math>\mathcal{A}_y</math> has density at least <math>\delta/2</math> in <math>S_y,</math> we return to the first iteration. For this to work, we need n-M to be large enough for the conclusion of the richness hypothesis to be satisfied. For every y such that <math>\mathcal{A}_y</math> has density <em>less</em> than <math>\delta/2</math> we put <math>\mathcal{A}_{1,y}</math> into the "error set" <math>\mathcal{A}''.</math>		For every y such that <math>\mathcal{A}_{1,y}</math> has density at least <math>\delta/2</math> in <math>S_y,</math> we return to the first iteration. For this to work, we need n-M to be large enough for the conclusion of the richness hypothesis to be satisfied. For every y such that <math>\mathcal{A}_y</math> has density <em>less</em> than <math>\delta/2</math> we put <math>\mathcal{A}_{1,y}</math> into the "error set" <math>\mathcal{A}''.</math>

	===How does the iteration finish?===		===How does the iteration finish?===

Gowers at 12:03, 16 March 2009

2009-03-16T12:03:55Z

← Older revision		Revision as of 05:03, 16 March 2009
Line 31:		Line 31:
	If <math>\mathcal{A}</math> has density less than <math>\delta</math> then we are done. Otherwise, by the richness hypothesis and averaging, there is a set Z of size M and a subspace <math>S_1\subset[k]^Z</math> such that the density of <math>x\in[k]^{[n]\setminus Z}</math> for which <math>\{x\}\times S_1\subset\mathcal{A}</math> is at least c.		If <math>\mathcal{A}</math> has density less than <math>\delta</math> then we are done. Otherwise, by the richness hypothesis and averaging, there is a set Z of size M and a subspace <math>S_1\subset[k]^Z</math> such that the density of <math>x\in[k]^{[n]\setminus Z}</math> for which <math>\{x\}\times S_1\subset\mathcal{A}</math> is at least c.

	~~Remove~~ all these subspaces <math>\{x\}\times S_1,</math> and partition <math>[k]^n</math> into the <math>3^M</math> subspaces of the form <math>S_y=\{y\}\times[k]^{[n]\setminus Z}</math> with <math>y\in[k]^Z.</math> Let <math>\mathcal{A}_1</math> be the set <math>\mathcal{A}</math> with the subspaces removed, and for each <math>y\in[k]^Z</math> let <math>\mathcal{A}_{1,y}</math> be the set of all <math>x\in[k]^{[n]\setminus Z}</math> such that <math>(x,y)\in\mathcal{A}_1.</math> Let <math>\mathcal{B}_1</math> be the set of all points <math>x\in[k]^{[n]\setminus Z}</math> such that <math>\{x\}\times S_1\subset\mathcal{A}.</math>		Put all these subspaces <math>\{x\}\times S_1</math> (which are disjoint) into <math>\mathcal{A}'</math> and partition <math>[k]^n</math> into the <math>k^M</math> subspaces of the form <math>S_y=\{y\}\times[k]^{[n]\setminus Z}</math> with <math>y\in[k]^Z.</math> Let <math>\mathcal{A}_1</math> be the set <math>\mathcal{A}</math> with the subspaces removed, and for each <math>y\in[k]^Z</math> let <math>\mathcal{A}_{1,y}</math> be the set of all <math>x\in[k]^{[n]\setminus Z}</math> such that <math>(x,y)\in\mathcal{A}_1.</math> Let <math>\mathcal{B}_1</math> be the set of all points <math>x\in[k]^{[n]\setminus Z}</math> such that <math>\{x\}\times S_1\subset\mathcal{A}.</math>

	===Second step of the iteration===		===Second step of the iteration===
Line 39:		Line 39:
	Now <math>\mathcal{B}_1=\bigcap_{y\in S_1}\mathcal{A}_y.</math> Therefore, since <math>\mathbf{K}</math> is hereditary and a sigma-algebra property, <math>\mathcal{B}_1\in\mathbf{K}.</math> And then, using the sigma-algebra assumption again, we have that <math>\mathcal{A}_{1,y}=\mathcal{A}_y\setminus\mathcal{B}_1\in\mathbf{K}.</math>		Now <math>\mathcal{B}_1=\bigcap_{y\in S_1}\mathcal{A}_y.</math> Therefore, since <math>\mathbf{K}</math> is hereditary and a sigma-algebra property, <math>\mathcal{B}_1\in\mathbf{K}.</math> And then, using the sigma-algebra assumption again, we have that <math>\mathcal{A}_{1,y}=\mathcal{A}_y\setminus\mathcal{B}_1\in\mathbf{K}.</math>

	<math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math>		For every y such that <math>\mathcal{A}_y</math> has density at least <math>\delta/2</math> in <math>S_y,</math> we return to the first iteration. For this to work, we need n-M to be large enough for the conclusion of the richness hypothesis to be satisfied. For every y such that <math>\mathcal{A}_y</math> has density <em>less</em> than <math>\delta/2</math> we put <math>\mathcal{A}_{1,y}</math> into the "error set" <math>\mathcal{A}''.</math>

			===How does the iteration finish?===

			At each stage of the iteration, we have split <math>\mathcal{A}</math> into three sets. One of these sets consists of parts of <math>\mathcal{A}</math> that have had density at most <math>\delta/2</math> in some subspace. Thus, the density of this set never exceeds <math>\delta/2.</math> Another part consists of a union of disjoint m-dimensional subspaces. The rest of <math>\mathcal{A}</math> we think of as the "unfinished" part. For this part, if we have reached the sth stage of the iteration, then we have a partition of <math>[k]^n</math> into subspaces of codimension <math>sM,</math> and any point in the unfinished part of <math>\mathcal{A}</math> belongs to a subspace from this collection inside which it has density at least <math>\delta/2.</math>

			It follows that, by the next iteration, the total density of the unfinished part is multiplied by a factor of at most <math>1-c,</math> since from each subspace into which we have partitioned the unfinished part we remove a union of subspaces of density at least <math>c.</math> Therefore, if we continue for <math>c^{-1}\log(2/\delta)</math> iterations, then the measure of the unfinished part is at most <math>\delta/2.</math> At this point we put it into <math>\mathcal{A}''.</math>

			In order to be able to continue for this many iterations, we need <math>n-Mc^{-1}\log(2/\delta)</math> to be sufficiently large for it to be possible to appeal to the richness hypothesis.

			<math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math>

Gowers: /* Second step of the iteration */

2009-03-16T11:40:12Z

Second step of the iteration

← Older revision		Revision as of 04:40, 16 March 2009
Line 37:		Line 37:
	Since <math>\mathbf{K}</math> is a hereditary property, the intersection <math>\mathcal{A}_y</math> of <math>\mathcal{A}</math> with <math>S_y</math> belongs to <math>\mathbf{K}</math> for every <math>y\in[k]^{[n]\setminus Z}.</math> If <math>y\notin S_1,</math> then no points have been removed from <math>\mathcal{A}_y,</math> so <math>\mathcal{A}_{1,y}=\mathcal{A}_y.</math> If <math>y\in S_1,</math> then <math>\mathcal{A}_{1,y}=\mathcal{A}_y\setminus\mathcal{B}_1.</math>		Since <math>\mathbf{K}</math> is a hereditary property, the intersection <math>\mathcal{A}_y</math> of <math>\mathcal{A}</math> with <math>S_y</math> belongs to <math>\mathbf{K}</math> for every <math>y\in[k]^{[n]\setminus Z}.</math> If <math>y\notin S_1,</math> then no points have been removed from <math>\mathcal{A}_y,</math> so <math>\mathcal{A}_{1,y}=\mathcal{A}_y.</math> If <math>y\in S_1,</math> then <math>\mathcal{A}_{1,y}=\mathcal{A}_y\setminus\mathcal{B}_1.</math>

	Now <math>\mathcal{B}_1=\bigcap_{y\in S_1}\mathcal{A}_y.</math> Therefore, since <math>\mathbf{K}</math> is hereditary and a sigma-algebra property, <math>\mathcal{B}_1\in\mathbf{K}.</math> And then, using ~~these two assumptions~~ again, we have that ~~<math>\mathcal{A}_y</math> and hence~~ <math>\mathcal{A}_{1,y}=\mathcal{A}_y\setminus\mathcal{B}_1\in\mathbf{K}.</math>		Now <math>\mathcal{B}_1=\bigcap_{y\in S_1}\mathcal{A}_y.</math> Therefore, since <math>\mathbf{K}</math> is hereditary and a sigma-algebra property, <math>\mathcal{B}_1\in\mathbf{K}.</math> And then, using the sigma-algebra assumption again, we have that <math>\mathcal{A}_{1,y}=\mathcal{A}_y\setminus\mathcal{B}_1\in\mathbf{K}.</math>

	<math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math>		<math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math>

Gowers at 11:33, 16 March 2009

2009-03-16T11:33:50Z

← Older revision		Revision as of 04:33, 16 March 2009
Line 19:		Line 19:
	The main result to be proved on this page is the following.		The main result to be proved on this page is the following.

	'''Lemma.''' Let <math>\mathbf{K}</math> be a Hales-Jewett property and suppose that <math>\mathbf{K}</math> is hereditary, subspace rich and a sigma-algebra property. Then for every <math>\delta>0</math> and every positive integer m there exists n such that for every set <math>\mathcal{A}\subset[k]^n</math> that belongs to <math>\mathbf{K}</math> there is a decomposition of <math>\mathcal{A}</math> into subsets <math>\mathcal{A}_1\cup\mathcal{A}_2</math> such that <math>\mathcal{A}_1</math> is a disjoint union of m-dimensional subspaces and <math>\mathcal{A}_2</math> has density at most <math>\delta.</math>		'''Lemma.''' Let <math>\mathbf{K}</math> be a Hales-Jewett property and suppose that <math>\mathbf{K}</math> is hereditary, subspace rich and a sigma-algebra property. Then for every <math>\delta>0</math> and every positive integer m there exists n such that for every set <math>\mathcal{A}\subset[k]^n</math> that belongs to <math>\mathbf{K}</math> there is a decomposition of <math>\mathcal{A}</math> into subsets <math>\mathcal{A}'\cup\mathcal{A}''</math> such that <math>\mathcal{A}'</math> is a disjoint union of m-dimensional subspaces and <math>\mathcal{A}''</math> has density at most <math>\delta.</math>

	To put this more loosely: every set that belongs to <math>\mathbf{K}</math> can be almost entirely partitioned into m-dimensional subspaces.		To put this more loosely: every set that belongs to <math>\mathbf{K}</math> can be almost entirely partitioned into m-dimensional subspaces.
Line 31:		Line 31:
	If <math>\mathcal{A}</math> has density less than <math>\delta</math> then we are done. Otherwise, by the richness hypothesis and averaging, there is a set Z of size M and a subspace <math>S_1\subset[k]^Z</math> such that the density of <math>x\in[k]^{[n]\setminus Z}</math> for which <math>\{x\}\times S_1\subset\mathcal{A}</math> is at least c.		If <math>\mathcal{A}</math> has density less than <math>\delta</math> then we are done. Otherwise, by the richness hypothesis and averaging, there is a set Z of size M and a subspace <math>S_1\subset[k]^Z</math> such that the density of <math>x\in[k]^{[n]\setminus Z}</math> for which <math>\{x\}\times S_1\subset\mathcal{A}</math> is at least c.

	Remove all these subspaces <math>\{x\}\times S_1,</math> and partition <math>[k]^n</math> into the <math>3^M</math> subspaces of the form <math>S_y=\{y\}\times[k]^{[n]\setminus Z}</math> with <math>y\in[k]^Z.</math>		Remove all these subspaces <math>\{x\}\times S_1,</math> and partition <math>[k]^n</math> into the <math>3^M</math> subspaces of the form <math>S_y=\{y\}\times[k]^{[n]\setminus Z}</math> with <math>y\in[k]^Z.</math> Let <math>\mathcal{A}_1</math> be the set <math>\mathcal{A}</math> with the subspaces removed, and for each <math>y\in[k]^Z</math> let <math>\mathcal{A}_{1,y}</math> be the set of all <math>x\in[k]^{[n]\setminus Z}</math> such that <math>(x,y)\in\mathcal{A}_1.</math> Let <math>\mathcal{B}_1</math> be the set of all points <math>x\in[k]^{[n]\setminus Z}</math> such that <math>\{x\}\times S_1\subset\mathcal{A}.</math>

	===Second step of the iteration===		===Second step of the iteration===

	Since <math>\mathbf{K}</math> is a hereditary property, the intersection <math>\mathcal{A}_y</math> of <math>\mathcal{A}</math> with <math>S_y</math> belongs to <math>\mathbf{K}</math> for every <math>y\in[k]^{[n]\setminus Z}.</math> <math></math><math></math><math></math><math></math><math></math>		Since <math>\mathbf{K}</math> is a hereditary property, the intersection <math>\mathcal{A}_y</math> of <math>\mathcal{A}</math> with <math>S_y</math> belongs to <math>\mathbf{K}</math> for every <math>y\in[k]^{[n]\setminus Z}.</math> If <math>y\notin S_1,</math> then no points have been removed from <math>\mathcal{A}_y,</math> so <math>\mathcal{A}_{1,y}=\mathcal{A}_y.</math> If <math>y\in S_1,</math> then <math>\mathcal{A}_{1,y}=\mathcal{A}_y\setminus\mathcal{B}_1.</math>

			Now <math>\mathcal{B}_1=\bigcap_{y\in S_1}\mathcal{A}_y.</math> Therefore, since <math>\mathbf{K}</math> is hereditary and a sigma-algebra property, <math>\mathcal{B}_1\in\mathbf{K}.</math> And then, using these two assumptions again, we have that <math>\mathcal{A}_y</math> and hence <math>\mathcal{A}_{1,y}=\mathcal{A}_y\setminus\mathcal{B}_1\in\mathbf{K}.</math>

			<math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math>

Gowers: /* Definitions and statement of result */

2009-03-16T11:10:33Z

Definitions and statement of result

← Older revision		Revision as of 04:10, 16 March 2009
Line 19:		Line 19:
	The main result to be proved on this page is the following.		The main result to be proved on this page is the following.

	'''Lemma.''' Let <math>\mathbf{K}</math> be a Hales-Jewett property and suppose that <math>\mathbf{K}</math> is hereditary, subspace-rich and a sigma-algebra property. Then for every <math>\delta>0</math> and every positive integer m there exists n such that for every set <math>\mathcal{A}\subset[k]^n</math> that belongs to <math>\mathbf{K}</math> there is a decomposition of <math>\mathcal{A}</math> into subsets <math>\mathcal{A}_1\cup\mathcal{A}_2</math> such that <math>\mathcal{A}_1</math> is a disjoint union of m-dimensional subspaces and <math>\mathcal{A}_2</math> has density at most <math>\delta.</math>		'''Lemma.''' Let <math>\mathbf{K}</math> be a Hales-Jewett property and suppose that <math>\mathbf{K}</math> is hereditary, subspace rich and a sigma-algebra property. Then for every <math>\delta>0</math> and every positive integer m there exists n such that for every set <math>\mathcal{A}\subset[k]^n</math> that belongs to <math>\mathbf{K}</math> there is a decomposition of <math>\mathcal{A}</math> into subsets <math>\mathcal{A}_1\cup\mathcal{A}_2</math> such that <math>\mathcal{A}_1</math> is a disjoint union of m-dimensional subspaces and <math>\mathcal{A}_2</math> has density at most <math>\delta.</math>

	To put this more loosely: every set that belongs to <math>\mathbf{K}</math> can be almost entirely partitioned into m-dimensional subspaces.		To put this more loosely: every set that belongs to <math>\mathbf{K}</math> can be almost entirely partitioned into m-dimensional subspaces.

Gowers: /* Definitions and statement of result */

2009-03-16T11:10:06Z

Definitions and statement of result

← Older revision		Revision as of 04:10, 16 March 2009
Line 19:		Line 19:
	The main result to be proved on this page is the following.		The main result to be proved on this page is the following.

	'''Lemma.''' Let <math>\mathbf{K}</math> be a hereditary ~~and~~ subspace-rich ~~Hales~~-~~Jewett~~ property. Then for every <math>\delta>0</math> and every positive integer m there exists n such that for every set <math>\mathcal{A}\subset[k]^n</math> that belongs to <math>\mathbf{K}</math> there is a decomposition of <math>\mathcal{A}</math> into subsets <math>\mathcal{A}_1\cup\mathcal{A}_2</math> such that <math>\mathcal{A}_1</math> is a disjoint union of m-dimensional subspaces and <math>\mathcal{A}_2</math> has density at most <math>\delta.</math>		'''Lemma.''' Let <math>\mathbf{K}</math> be a Hales-Jewett property and suppose that <math>\mathbf{K}</math> is hereditary, subspace-rich and a sigma-algebra property. Then for every <math>\delta>0</math> and every positive integer m there exists n such that for every set <math>\mathcal{A}\subset[k]^n</math> that belongs to <math>\mathbf{K}</math> there is a decomposition of <math>\mathcal{A}</math> into subsets <math>\mathcal{A}_1\cup\mathcal{A}_2</math> such that <math>\mathcal{A}_1</math> is a disjoint union of m-dimensional subspaces and <math>\mathcal{A}_2</math> has density at most <math>\delta.</math>

	To put this more loosely: every set that belongs to <math>\mathbf{K}</math> can be almost entirely partitioned into m-dimensional subspaces.		To put this more loosely: every set that belongs to <math>\mathbf{K}</math> can be almost entirely partitioned into m-dimensional subspaces.

Gowers: /* Definitions and statement of result */

2009-03-16T11:08:16Z

Definitions and statement of result

← Older revision		Revision as of 04:08, 16 March 2009
Line 15:		Line 15:
	Note that since <math>\mathbf{K}</math> is a Hales-Jewett property we have a similar hypothesis (that is slightly less convenient to state) for subsets of arbitrary finite-dimensional combinatorial subspaces.		Note that since <math>\mathbf{K}</math> is a Hales-Jewett property we have a similar hypothesis (that is slightly less convenient to state) for subsets of arbitrary finite-dimensional combinatorial subspaces.

	'''Sigma-algebra ~~property~~.''' We shall say that <math>\mathbf{K}</math> is a ''sigma-algebra'' if whenever <math>\mathcal{A}</math> and <math>\mathcal{A}'</math> are subsets of a subspace S that belong to <math>\mathbf{K},</math> then <math>\mathcal{A}\cap\mathcal{A'}</math> and <math>\mathcal{A}\setminus\mathcal{A'}</math> belong to <math>\mathbf{K}.</math>		'''Sigma-algebra properties.''' We shall say that <math>\mathbf{K}</math> is a ''sigma-algebra property'' if whenever <math>\mathcal{A}</math> and <math>\mathcal{A}'</math> are subsets of a subspace S that belong to <math>\mathbf{K},</math> then <math>\mathcal{A}\cap\mathcal{A'}</math> and <math>\mathcal{A}\setminus\mathcal{A'}</math> belong to <math>\mathbf{K}.</math>

	The main result to be proved on this page is the following.		The main result to be proved on this page is the following.

Gowers: /* Definitions and statement of result */

2009-03-16T11:07:35Z

Definitions and statement of result

← Older revision		Revision as of 04:07, 16 March 2009
Line 7:		Line 7:
	'''Hales-Jewett properties.''' Let <math>\mathbf{K}</math> be a collection of subsets of combinatorial subspaces of <math>[k]^n.</math> We shall say that <math>\mathbf{K}</math> is a ''Hales-Jewett property'' if it is invariant under isomorphisms between subspaces: that is, if <math>\phi</math> is an isomorphism from <math>S_1</math> to <math>S_2</math> and <math>\mathcal{A}\subset S_1</math> is a set in <math>\mathbf{K},</math> then <math>\phi(\mathcal{A})\in\mathbf{K}</math> as well.		'''Hales-Jewett properties.''' Let <math>\mathbf{K}</math> be a collection of subsets of combinatorial subspaces of <math>[k]^n.</math> We shall say that <math>\mathbf{K}</math> is a ''Hales-Jewett property'' if it is invariant under isomorphisms between subspaces: that is, if <math>\phi</math> is an isomorphism from <math>S_1</math> to <math>S_2</math> and <math>\mathcal{A}\subset S_1</math> is a set in <math>\mathbf{K},</math> then <math>\phi(\mathcal{A})\in\mathbf{K}</math> as well.

	'''Hereditary properties.''' We say that a Hales-Jewett property <math>\mathbf{K}</math> is ''hereditary'' if <math>\mathcal{A}\cap S\in\mathbf{K}</math> whenever <math>\mathcal{A}</math> is a subset of a combinatorial subspace T, <math>\mathcal{A}\in\mathbf{K}</math> and S is a [[combinatorial subspace]] of T. We shall call the property <math>\mathbf{K}</math> ''subspace rich'' if for every m and every <math>\delta</math> there are constants <math>M=M(m,\delta)</math> and <math>c=c(m,\delta)>0</math> such that the following statement holds for all sufficiently large n.		'''Hereditary properties.''' We say that a Hales-Jewett property <math>\mathbf{K}</math> is ''hereditary'' if <math>\mathcal{A}\cap S\in\mathbf{K}</math> whenever <math>\mathcal{A}</math> is a subset of a combinatorial subspace T, <math>\mathcal{A}\in\mathbf{K}</math> and S is a [[combinatorial subspace]] of T.

	'''Richness hypothesis.''' Let <math>\mathcal{A}\in\mathbf{K}</math> have density <math>\delta</math> in <math>[k]^n.</math> Choose a random M-dimensional subspace <math>S_0</math> of <math>[k]^n</math> by randomly fixing all coordinates outside a randomly chosen set Z of size M. Next, choose a subspace <math>S_1\subset S_0</math> of dimension m, uniformly at random from all such subspaces. Then <math>S_1\subset\mathcal{A}</math> with probability at least <math>c.</math>		'''Richness hypothesis.''' We shall call the property <math>\mathbf{K}</math> ''subspace rich'' if for every m and every <math>\delta</math> there are constants <math>M=M(m,\delta)</math> and <math>c=c(m,\delta)>0</math> such that the following statement holds for all sufficiently large n.

			*Let <math>\mathcal{A}\in\mathbf{K}</math> have density <math>\delta</math> in <math>[k]^n.</math> Choose a random M-dimensional subspace <math>S_0</math> of <math>[k]^n</math> by randomly fixing all coordinates outside a randomly chosen set Z of size M. Next, choose a subspace <math>S_1\subset S_0</math> of dimension m, uniformly at random from all such subspaces. Then <math>S_1\subset\mathcal{A}</math> with probability at least <math>c.</math>

	Note that since <math>\mathbf{K}</math> is a Hales-Jewett property we have a similar hypothesis (that is slightly less convenient to state) for subsets of arbitrary finite-dimensional combinatorial subspaces.		Note that since <math>\mathbf{K}</math> is a Hales-Jewett property we have a similar hypothesis (that is slightly less convenient to state) for subsets of arbitrary finite-dimensional combinatorial subspaces.

Gowers: /* Definitions and statement of result */ Added sigma-algebra property

2009-03-16T11:06:36Z

Definitions and statement of result: Added sigma-algebra property

← Older revision		Revision as of 04:06, 16 March 2009
Line 5:		Line 5:
	==Definitions and statement of result==		==Definitions and statement of result==

	Let <math>\mathbf{K}</math> be a collection of subsets of combinatorial subspaces of <math>[k]^n.</math> We shall say that <math>\mathbf{K}</math> is a ''Hales-Jewett property'' if it is invariant under isomorphisms between subspaces: that is, if <math>\phi</math> is an isomorphism from <math>S_1</math> to <math>S_2</math> and <math>\mathcal{A}\subset S_1</math> is a set in <math>\mathbf{K},</math> then <math>\phi(\mathcal{A})\in\mathbf{K}</math> as well.		'''Hales-Jewett properties.''' Let <math>\mathbf{K}</math> be a collection of subsets of combinatorial subspaces of <math>[k]^n.</math> We shall say that <math>\mathbf{K}</math> is a ''Hales-Jewett property'' if it is invariant under isomorphisms between subspaces: that is, if <math>\phi</math> is an isomorphism from <math>S_1</math> to <math>S_2</math> and <math>\mathcal{A}\subset S_1</math> is a set in <math>\mathbf{K},</math> then <math>\phi(\mathcal{A})\in\mathbf{K}</math> as well.

	We say that a Hales-Jewett property <math>\mathbf{K}</math> is ''hereditary'' if <math>\mathcal{A}\cap S\in\mathbf{K}</math> whenever <math>\mathcal{A}</math> is a subset of a combinatorial subspace T, <math>\mathcal{A}\in\mathbf{K}</math> and S is a [[combinatorial subspace]] of T. We shall call the property <math>\mathbf{K}</math> ''subspace rich'' if for every m and every <math>\delta</math> there are constants <math>M=M(m,\delta)</math> and <math>c=c(m,\delta)>0</math> such that the following statement holds for all sufficiently large n.		'''Hereditary properties.''' We say that a Hales-Jewett property <math>\mathbf{K}</math> is ''hereditary'' if <math>\mathcal{A}\cap S\in\mathbf{K}</math> whenever <math>\mathcal{A}</math> is a subset of a combinatorial subspace T, <math>\mathcal{A}\in\mathbf{K}</math> and S is a [[combinatorial subspace]] of T. We shall call the property <math>\mathbf{K}</math> ''subspace rich'' if for every m and every <math>\delta</math> there are constants <math>M=M(m,\delta)</math> and <math>c=c(m,\delta)>0</math> such that the following statement holds for all sufficiently large n.

	'''Richness hypothesis.''' Let <math>\mathcal{A}\in\mathbf{K}</math> have density <math>\delta</math> in <math>[k]^n.</math> Choose a random M-dimensional subspace <math>S_0</math> of <math>[k]^n</math> by randomly fixing all coordinates outside a randomly chosen set Z of size M. Next, choose a subspace <math>S_1\subset S_0</math> of dimension m, uniformly at random from all such subspaces. Then <math>S_1\subset\mathcal{A}</math> with probability at least <math>c.</math>		'''Richness hypothesis.''' Let <math>\mathcal{A}\in\mathbf{K}</math> have density <math>\delta</math> in <math>[k]^n.</math> Choose a random M-dimensional subspace <math>S_0</math> of <math>[k]^n</math> by randomly fixing all coordinates outside a randomly chosen set Z of size M. Next, choose a subspace <math>S_1\subset S_0</math> of dimension m, uniformly at random from all such subspaces. Then <math>S_1\subset\mathcal{A}</math> with probability at least <math>c.</math>

	Note that since <math>\mathbf{K}</math> is a Hales-Jewett property we have a similar hypothesis (that is slightly less convenient to state) for subsets of arbitrary finite-dimensional combinatorial subspaces.		Note that since <math>\mathbf{K}</math> is a Hales-Jewett property we have a similar hypothesis (that is slightly less convenient to state) for subsets of arbitrary finite-dimensional combinatorial subspaces.

			'''Sigma-algebra property.''' We shall say that <math>\mathbf{K}</math> is a ''sigma-algebra'' if whenever <math>\mathcal{A}</math> and <math>\mathcal{A}'</math> are subsets of a subspace S that belong to <math>\mathbf{K},</math> then <math>\mathcal{A}\cap\mathcal{A'}</math> and <math>\mathcal{A}\setminus\mathcal{A'}</math> belong to <math>\mathbf{K}.</math>

	The main result to be proved on this page is the following.		The main result to be proved on this page is the following.