sequence needs work

N. J. A. Sloane njas at
Tue May 23 21:34:17 CEST 2000

Here is a classical combinatorial problem,
which will produce a sequence,
which will probably be new.

Fix n, n=1,2,3,4,...

*** Find the max number of binary vectors of length n
*** such that the unions of any 2 distinct vectors
*** are all distinct.

For n=1 we take {0,1}, so a(1)=2

For n=2 we can take { 00, 01, 10 }, so a(2)=3

For n=3 take {000, 001, 010, 100 }, and a(3)=4.
[the six unions of pairs of these vectors are
001, 010, 100, 011, 101, 110,
which indeed are all different]

For n=4 we could try {0000, 0001, 0010, 0100, 1000}, giving
a(4) >= 5, and i'm pretty sure that's optimal

For n=5 the answer is 6, 7 or 8.

I think it is known that this grows exponentially with n
(Erdos, Frankl, Furedi, JCT 1982 vol. A33, 158-162).

But i'm interested in finding the exact values
of the first few cases so as to get a sequence for the database.

I'm also interested in seeing what the optimal codes look like.

If anyone cares to do some computing on this problem, please let me
know what you find.

 Neil J. A. Sloane, njas at,
 AT&T Shannon Lab, 180 Park Ave, Room C233,
 Florham Park, NJ 07932-0971 USA.
 Home page:
 Office: (973) 360 8415; fax: (973) 360 8178; virtual office: (732) 828 6098

More information about the SeqFan mailing list