Line: Difference between revisions
correct apparent typo in example of geometric line that is not a combinatorial line |
mNo edit summary |
||
| Line 1: | Line 1: | ||
There are three types of lines in <math>[3]^n</math>: ''combinatorial lines'', ''geometric lines'', and ''algebraic lines''. ( | There are three types of lines in <math>[3]^n</math>: ''combinatorial lines'', ''geometric lines'', and ''algebraic lines''. (There are obvious analogues for all three notions defined on <math>[k]^n</math> for more general values of k, including k=2.) | ||
For us, the most important (and most restrictive) notion is that of a ''combinatorial line'', which is a set of three points in <math>[3]^n</math>, formed by taking a string with one or more wildcards <math>\ast</math> in it, e.g., <math>112\!\ast\!\!1\!\ast\!\ast3\ldots</math>, and replacing those wildcards by <math>1, 2</math> and <math>3</math>, respectively. In the example given, the resulting combinatorial line is: <math>\{ 11211113\ldots, 11221223\ldots, 11231333\ldots \}</math>. Sets without any combinatorial lines are called ''line-free''. The higher-dimensional analogue of a combinatorial line is a [[combinatorial subspace]]. More precisely, a d-dimensional combinatorial subspace is obtained by taking d disjoint subsets <math>W_1,\dots,W_d</math> of <math>[n],</math> fixing the values of all coordinates outside these subsets, and taking all points that equal the fixed values outside the <math>W_i</math> and are constant on each <math>W_i.</math> Sometimes one adds the restriction that the maximum of each <math>W_i</math> is less than the minimum of <math>W_{i+1}</math>. (In particular, the [[Hales-Jewett theorem]] or its [[DHJ(3)|density analogue]] can be straightforwardly generalized to yield a monochromatic subspace of this more stronger kind.) | For us, the most important (and most restrictive) notion is that of a ''combinatorial line'', which is a set of three points in <math>[3]^n</math>, formed by taking a string with one or more wildcards <math>\ast</math> in it, e.g., <math>112\!\ast\!\!1\!\ast\!\ast3\ldots</math>, and replacing those wildcards by <math>1, 2</math> and <math>3</math>, respectively. In the example given, the resulting combinatorial line is: <math>\{ 11211113\ldots, 11221223\ldots, 11231333\ldots \}</math>. Sets without any combinatorial lines are called ''line-free''. The higher-dimensional analogue of a combinatorial line is a [[combinatorial subspace]]. More precisely, a d-dimensional combinatorial subspace is obtained by taking d disjoint subsets <math>W_1,\dots,W_d</math> of <math>[n],</math> fixing the values of all coordinates outside these subsets, and taking all points that equal the fixed values outside the <math>W_i</math> and are constant on each <math>W_i.</math> Sometimes one adds the restriction that the maximum of each <math>W_i</math> is less than the minimum of <math>W_{i+1}</math>. (In particular, the [[Hales-Jewett theorem]] or its [[DHJ(3)|density analogue]] can be straightforwardly generalized to yield a monochromatic subspace of this more stronger kind.) | ||
Revision as of 05:00, 22 February 2009
There are three types of lines in [math]\displaystyle{ [3]^n }[/math]: combinatorial lines, geometric lines, and algebraic lines. (There are obvious analogues for all three notions defined on [math]\displaystyle{ [k]^n }[/math] for more general values of k, including k=2.)
For us, the most important (and most restrictive) notion is that of a combinatorial line, which is a set of three points in [math]\displaystyle{ [3]^n }[/math], formed by taking a string with one or more wildcards [math]\displaystyle{ \ast }[/math] in it, e.g., [math]\displaystyle{ 112\!\ast\!\!1\!\ast\!\ast3\ldots }[/math], and replacing those wildcards by [math]\displaystyle{ 1, 2 }[/math] and [math]\displaystyle{ 3 }[/math], respectively. In the example given, the resulting combinatorial line is: [math]\displaystyle{ \{ 11211113\ldots, 11221223\ldots, 11231333\ldots \} }[/math]. Sets without any combinatorial lines are called line-free. The higher-dimensional analogue of a combinatorial line is a combinatorial subspace. More precisely, a d-dimensional combinatorial subspace is obtained by taking d disjoint subsets [math]\displaystyle{ W_1,\dots,W_d }[/math] of [math]\displaystyle{ [n], }[/math] fixing the values of all coordinates outside these subsets, and taking all points that equal the fixed values outside the [math]\displaystyle{ W_i }[/math] and are constant on each [math]\displaystyle{ W_i. }[/math] Sometimes one adds the restriction that the maximum of each [math]\displaystyle{ W_i }[/math] is less than the minimum of [math]\displaystyle{ W_{i+1} }[/math]. (In particular, the Hales-Jewett theorem or its density analogue can be straightforwardly generalized to yield a monochromatic subspace of this more stronger kind.)
The most general notion of a line is that of an algebraic line, which is a set of three points of the form x, x+r, x+2r, where we identify [math]\displaystyle{ [3]^n }[/math] with [math]\displaystyle{ ({\Bbb Z}/3{\Bbb Z})^n }[/math] and r is non-zero. Every combinatorial line is an algebraic line, but not conversely. For instance [math]\displaystyle{ \{23, 31, 12\} }[/math] is an algebraic line (but not a combinatorial or geometric line). Sets without any algebraic lines are called cap-sets.
Intermediate between these is the notion of a geometric line: an arithmetic progression in [math]\displaystyle{ [3]^n }[/math], which we now identify as a subset of [math]\displaystyle{ {\Bbb Z}^n }[/math]. Every combinatorial line is geometric, and every geometric line is algebraic, but not conversely. For instance, [math]\displaystyle{ \{ 31, 22, 13 \} }[/math] is a geometric line (and thus algebraic) but not a combinatorial line. Sets without any geometric lines are called Moser sets: see Moser's cube problem. One can view geometric lines as being like combinatorial lines, but with a second wildcard y which goes from 3 to 1 whilst x goes from 1 to 3, e.g. xx2yy gives the geometric line 11233, 22222, 33211.
