# Line

There are three types of lines in $^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 $^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 $W_i$ and are constant on each $W_i.$ Sometimes one adds the restriction that the maximum of each $W_i$ is less than the minimum of $W_{i+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 $^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 $^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.