|
%I #15 Jun 09 2018 08:18:26
%S 1,2,6,18,52,150,450
%N 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.)
%C The density Hales-Jewett theorem implies that a(n) = o(3^n). a(n) is studied further in the polymath1 project, see link below.
%H H. Furstenberg, Y. Katznelson, <a href="http://dx.doi.org/10.1016/0012-365X(89)90089-7">A density version of the Hales-Jewett theorem for k=3</a>, Graph Theory and Combinatorics (Cambridge, 1988). Discr. Math. 75 (1989) no. 1-3, 227-241.
%H H. Furstenberg and Y. Katznelson, <a href="http://dx.doi.org/10.1007/BF03041066">A density version of the Hales-Jewett theorem</a>, J. Anal. Math. 57 (1991), 64-119.
%H K. O'Bryant, <a href="http://arxiv.org/abs/1410.4900">Sets of natural numbers with proscribed subsets</a>, arXiv:1410.4900 [math.NT], 2014-2015.
%H K. O'Bryant, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/OBryant/obr3.html">Sets of Natural Numbers with Proscribed Subsets</a>, J. Int. Seq. 18 (2015) # 15.7.7
%H D. H. J. Polymath, <a href="http://arxiv.org/abs/1002.0374">Density Hales-Jewett and Moser numbers</a>, arXiv:1002.0374 [math.CO]
%H Polymath1 Project, <a href="http://michaelnielsen.org/polymath1/index.php?title=Main_Page">Wiki Main Page</a>
%H Terence Tao, <a href="http://terrytao.wordpress.com/2009/02/05/upper-and-lower-bounds-for-the-density-hales-jewett-problem/">Bounds for the first few density Hales-Jewett numbers, and related quantities</a> [From _Jonathan Vos Post_, Feb 20 2009]
%e For n=2, one example that shows a(2) is at least 6 is { 11, 13, 22, 23, 31, 32 }.
%Y Bounded below by A003142. Cf. A000244, A090245.
%K hard,more,nonn
%O 0,2
%A _Terence Tao_, Feb 20 2009
|
