Upper and lower bounds

Upper and lower bounds for [math]\displaystyle{ c_n }[/math] for small values of n.

Basic constructions

For all [math]\displaystyle{ n \geq 1 }[/math], a basic example of a mostly line-free set is

[math]\displaystyle{ D_n := \{ (x_1,\ldots,x_n) \in [3]^n: \sum_{i=1}^n x_i = 0 \ \operatorname{mod}\ 3 \} }[/math].

This has cardinality [math]\displaystyle{ |D_n| = 2 \times 3^{n-1} }[/math]. The only lines in [math]\displaystyle{ D_n }[/math] are those with

1. A number of wildcards equal to a multiple of three;
2. The number of 1s equal to the number of 2s modulo 3.

One way to construct line-free sets is to start with [math]\displaystyle{ D_n }[/math] and remove some additional points.

Another useful construction proceeds by using the slices [math]\displaystyle{ \Gamma_{a,b,c} \subset [3]^n }[/math] for [math]\displaystyle{ (a,b,c) }[/math] in the triangular grid

[math]\displaystyle{ \Delta_n := \{ (a,b,c) \in {\Bbb Z}_+^3: a+b+c = n \}, }[/math].

where [math]\displaystyle{ \Gamma_{a,b,c} }[/math] is defined as the strings in [math]\displaystyle{ [3]^n }[/math] with [math]\displaystyle{ a }[/math] 1s, [math]\displaystyle{ b }[/math] 2s, and [math]\displaystyle{ c }[/math] 3s. Note that

[math]\displaystyle{ |\Gamma_{a,b,c}| = \frac{n!}{a! b! c!}. }[/math]

Given any set [math]\displaystyle{ B \subset \Delta_n }[/math] that avoids equilateral triangles [math]\displaystyle{ (a+r,b,c), (a,b+r,c), (a,b,c+r) }[/math], the set

[math]\displaystyle{ \Gamma_B := \bigcup_{(a,b,c) \in B} \Gamma_{a,b,c} }[/math]

is line-free and has cardinality

[math]\displaystyle{ |\Gamma_B| = \sum_{(a,b,c) \in B} \frac{n!}{a! b! c!}, }[/math]

and thus provides a lower bound for [math]\displaystyle{ c_n }[/math]:

[math]\displaystyle{ c_n \geq \sum_{(a,b,c) \in B} \frac{n!}{a! b! c!}. }[/math]

All lower bounds have proceeded so far by choosing a good set of B. Note that [math]\displaystyle{ D_n }[/math] is the same as [math]\displaystyle{ \Gamma_{B_n} }[/math], where [math]\displaystyle{ B_n }[/math] consists of those triples [math]\displaystyle{ (a,b,c) \in \Delta_n }[/math] in which [math]\displaystyle{ a \neq b\ \operatorname{mod}\ 3 }[/math].

Note that if one takes a line-free set and permutes the alphabet [math]\displaystyle{ \{1,2,3\} }[/math] in any fashion (e.g. replacing all 1s by 2s and vice versa), one also gets a line-free set. This potentially gives six examples from any given starting example of a line-free set, though in practice there is enough symmetry that the total number of examples produced this way is less than six. (These six examples also correspond to the six symmetries of the triangular grid [math]\displaystyle{ \Delta_n }[/math] formed by rotation and reflection.)

Another symmetry comes from permuting the [math]\displaystyle{ n }[/math] indices in the strings of [math]\displaystyle{ [3]^n }[/math] (e.g. replacing every string by its reversal). But the sets [math]\displaystyle{ \Gamma_B }[/math] are automatically invariant under such permutations and thus do not produce new line-free sets via this symmetry.

The basic upper bound

Because [math]\displaystyle{ [3]^{n+1} }[/math] can be expressed as the union of three copies of [math]\displaystyle{ [3]^n }[/math], we have the basic upper bound

[math]\displaystyle{ c_{n+1} \leq 3 c_n. }[/math]

Note that equality only occurs if one can find an [math]\displaystyle{ n+1 }[/math]-dimensional line-free set such that every n-dimensional slice has the maximum possible cardinality of [math]\displaystyle{ c_n }[/math].

n=0

Clearly [math]\displaystyle{ c_0=1 }[/math].

n=1

The three sets [math]\displaystyle{ D_1 = \{1,2\} }[/math], [math]\displaystyle{ \{2,3\} }[/math], and [math]\displaystyle{ \{1,3\} }[/math] are the only two-element sets which are line-free in [math]\displaystyle{ [3]^1 }[/math], and there are no three-element sets, so [math]\displaystyle{ c_1=2 }[/math].

n=2

There are three six-element sets in [math]\displaystyle{ [3]^2 }[/math] which are line-free, which we denote [math]\displaystyle{ x }[/math], [math]\displaystyle{ y }[/math], and [math]\displaystyle{ z }[/math], and are displayed graphically as follows.

    13 .. 33
x = 12 22 ..
    .. 21 31

    .. 23 33
y = 12 .. 32
    11 21 ..

    13 .. 33
z = 12 22 ..
    .. 21 31

[math]\displaystyle{ z }[/math] is also the same as [math]\displaystyle{ D_2 }[/math]. Combining this with the basic upper bound