cp's OEIS Frontend

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.)

%I A156989 #23 Sep 05 2025 06:00:18
%S A156989 1,2,6,18,52,150,450
%N 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.)
%C A156989 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 A156989 Thomas Bloom, <a href="https://www.erdosproblems.com/171">Problem 171</a>, Erdős Problems.
%H A156989 Hillel H. Furstenberg and Yitzhak 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 A156989 Hillel H. Furstenberg and Yitzhak 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 A156989 Kevin 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 A156989 Kevin 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 A156989 D. H. J. Polymath, <a href="http://arxiv.org/abs/1002.0374">Density Hales-Jewett and Moser numbers</a>, arXiv:1002.0374 [math.CO], 2010.
%H A156989 Polymath1 Project, <a href="http://michaelnielsen.org/polymath1/index.php?title=Main_Page">Wiki Main Page</a>
%H A156989 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>
%H A156989 Terence Tao, <a href="https://github.com/teorth/erdosproblems/blob/main/README.md#table">Erdős problem database</a>, see no. 171.
%e A156989 For n=2, one example that shows a(2) is at least 6 is { 11, 13, 22, 23, 31, 32 }.
%Y A156989 Bounded below by A003142. Cf. A000244, A090245.
%K A156989 hard,more,nonn,changed
%O A156989 0,2
%A A156989 _Terence Tao_, Feb 20 2009