|
| |
|
|
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 Hales-Jewett theorem implies that a(n)=o(3^n). a(n) is studied further in the polymath1 project, see link below
|
|
|
REFERENCES
| H. Furstenberg and Y. Katznelson, "A density version of the Hales-Jewett theorem for k=3", Graph Theory and Combinatorics (Cambridge, 1988). Discrete Math. 75 (1989), no. 1-3, 227-241.
H. Furstenberg and Y. Katznelson, "A density version of the Hales-Jewett theorem", J. Anal. Math. 57 (1991), 64-119.
|
|
|
LINKS
| H. Furstenberg, Y. Katznelson, A density version of the Hales-Jewett theorem for k=3, Discr. Math. 75 (1989) no. 1-3, 227-241.
D. H. J. Polymath, Density Hales-Jewett and Moser numbers, arXiv:1002.0374 [math.CO]
Polymath1 Project, Wiki Main Page
Terence Tao, Bounds for the first few density Hales-Jewett numbers, and related quantities [From Jonathan Vos Post (jvospost3(AT)gmail.com), 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. A090245, A000244.
Sequence in context: A128104 A027059 A078484 * A077935 A077835 A077984
Adjacent sequences: A156986 A156987 A156988 * A156990 A156991 A156992
|
|
|
KEYWORD
| hard,more,nonn
|
|
|
AUTHOR
| Terence Tao (tao(AT)math.ucla.edu), Feb 20 2009
|
|
|
EXTENSIONS
| Replaced link to cached arXiv URL by link to the abstract - R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Mar 01 2010
|
| |
|
|
