From Polymath Wiki
(Redirected from Combinatorial line)
Jump to: navigation, search

There are three types of lines in [math][3]^n[/math]: combinatorial lines, geometric lines, and algebraic lines. (For all three notions there are obvious analogues 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 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][3]^n[/math] with [math]({\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]\{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][3]^n[/math], which we now identify as a subset of [math]{\Bbb Z}^n[/math]. Every combinatorial line is geometric, and every geometric line is algebraic, but not conversely. For instance, [math]\{ 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.