Line

From Polymath1Wiki

Jump to: navigation, search

There are three types of lines in [3]n: combinatorial lines, geometric lines, and algebraic lines. (For all three notions there are obvious analogues defined on [k]n 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 [3]n, formed by taking a string with one or more wildcards \ast in it, e.g., 112\!\ast\!\!1\!\ast\!\ast3\ldots, and replacing those wildcards by 1,2 and 3, respectively. In the example given, the resulting combinatorial line is: \{ 11211113\ldots, 11221223\ldots, 11231333\ldots \}. 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 W_1,\dots,W_d of [n], fixing the values of all coordinates outside these subsets, and taking all points that equal the fixed values outside the Wi and are constant on each Wi. Sometimes one adds the restriction that the maximum of each Wi is less than the minimum of Wi + 1. (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 [3]n with ({\Bbb Z}/3{\Bbb Z})^n and r is non-zero. Every combinatorial line is an algebraic line, but not conversely. For instance {23,31,12} 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 [3]n, which we now identify as a subset of {\Bbb Z}^n. Every combinatorial line is geometric, and every geometric line is algebraic, but not conversely. For instance, {31,22,13} 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.

Personal tools