[seqfan] Terry Tao's recent sequence A156989 subsumes mine A156762, unless...

[Jonathan Post]

Terry Tao's recent sequence subsumes mine, unless mine has anything in
description or comments that might usefully be carried into his.

%I A156989
%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
%D A156989 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, Y. Katznelson, "A density version of the Hales-Jewett
theorem", J. Anal. Math. 57 (1991), 64-119.
%H A156989 <a href="http://michaelnielsen.org/polymath1/index.php?title=Main_Page">Polymath1
project wiki</a>
%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
%K A156989 bref,hard,more,nonn,new
%O A156989 0,2
%A A156989 Terence Tao (tao(AT)math.ucla.edu), Feb 20 2009

A156762  	 	 The largest size of a set in [3]^n without a combinatorial line.
	1, 2, 6, 18, 52

	OFFSET 	
0,2
	
	COMMENT 	
For any positive integer n, let [3]^n be the set of strings of length
n consisting of 1s, 2s, and 3s, and define a combinatorial line to be
a triple of such strings arising by taking a string in {1,2,3,x}^n
with at least one wildcard x, and substituting x=1, x=2, x=3 in that
string (e.g. xx1x3 would give the combinatorial line {11113, 22123,
33133}. Call a set A contained in [3]^n of strings line-free if it
contains no combinatorial lines, and let a(n) be the size of the
largest set A which is line-free. We then have Density Hales-Jewett
theorem (k=3): a(n) = o(3^n), i.e. lim[as n approaches infinity]
a(n)/(3^n) = 0. 150 <= a(5) <= 154. 450 <= a(6) <= 462. More
exposition, proofs, and upper and lower bounds in the Tao blog linked
to.

	LINKS 	
Terence Tao, Bounds for the first few density Hales-Jewett numbers,
and related quantities

	CROSSREFS 	
Cf. A000244.

	KEYWORD 	
more,nonn,new

	AUTHOR 	
Jonathan Vos Post (jvospost3(AT)gmail.com), Feb 15 2009