

A156989


Largest size of a subset of {1,2,3}^n that does not contain any combinatorial lines (i.e., strings formed by 1, 2, 3, and at least one instance of a wildcard x, with x then substituted for 1, 2, or 3, e.g. 12x3x gives the combinatorial line 12131, 12232, 12333.)


2




OFFSET

0,2


COMMENTS

The density HalesJewett theorem implies that a(n) = o(3^n). a(n) is studied further in the polymath1 project, see link below.


LINKS

Table of n, a(n) for n=0..6.
H. Furstenberg, Y. Katznelson, A density version of the HalesJewett theorem for k=3, Graph Theory and Combinatorics (Cambridge, 1988). Discr. Math. 75 (1989) no. 13, 227241.
H. Furstenberg and Y. Katznelson, A density version of the HalesJewett theorem, J. Anal. Math. 57 (1991), 64119.
K. O'Bryant, Sets of natural numbers with proscribed subsets, arXiv:1410.4900 [math.NT], 20142015.
D. H. J. Polymath, Density HalesJewett and Moser numbers, arXiv:1002.0374 [math.CO]
Polymath1 Project, Wiki Main Page
Terence Tao, Bounds for the first few density HalesJewett numbers, and related quantities [From Jonathan Vos Post, Feb 20 2009]


EXAMPLE

For n=2, one example that shows a(2) is at least 6 is { 11, 13, 22, 23, 31, 32 }.


CROSSREFS

Bounded below by A003142. Cf. A000244, A090245.
Sequence in context: A128104 A027059 A078484 * A077935 A077835 A077984
Adjacent sequences: A156986 A156987 A156988 * A156990 A156991 A156992


KEYWORD

hard,more,nonn


AUTHOR

Terence Tao, Feb 20 2009


STATUS

approved



