A286874 Maximal number of binary vectors of length n such that the union (or bitwise OR) of any 2 distinct vectors does not contain any other vector.

1, 2, 2, 3, 4, 5, 6, 7, 8, 12, 13, 17, 20, 26

Offset: 0

Author

Dmitry Kamenetsky, Aug 02 2017

Keywords

• nonn
• hard
• more

Comments

The concatenation of these vectors produces a 2-disjunct matrix.

a(10) >= 13. Here is a candidate solution: {0101000001 0001000110 1000100001 0010000011 1001010000 0010110000 1000001010 0011001000 0100100010 1110000000 0100010100 0000011001 0000101100}. - Dmitry Kamenetsky, Sep 07 2017

a(11) >= 17. Here is a candidate solution: {01000010100 10000100100 00000001110 00010010001 10000011000 01000001001 00001010010 00010101000 00100110000 00100000101 00000100011 00101001000 10110000000 11000000010 00011000100 10001000001 01001100000}. - Dmitry Kamenetsky, Sep 07 2017

The best lower bounds known for the next terms a(14)-a(16) are 28, 40 (corrected by Steinar H. Gunderson, Jul 22 2025) and 45 (see attached files for the solutions).

The bounds for a(10) and a(11) are tight, by the Z3 SMT solver. - Steinar H. Gunderson, Jun 23 2025

a(12)-a(13) were determined by exhaustive parallel search. - Steinar H. Gunderson, Jul 17 2025

Examples

			Here is a solution for n=9: {110001000 001001010 001100100 100100010 100010100 000010011 101000001 011010000 000111000 010100001 010000110 000001101}.
		

Links

• Johan V. Dinesen, Lower bound and solution for a(15)
• P. Erdös, P. Frankl and Z. Füredi, Families of finite sets in which no set is covered by the union of two others, J. Combin. Theory, A33 (1982), 158-166.
• Dmitry Kamenetsky, Lower bounds and their solutions for a(12-16)
• W. Kautz and R. Singleton, Nonrandom binary superimposed codes, IEEE Transactions on Information Theory, Volume: 10, Issue: 4, October 1964.
• Wikipedia, Disjunct Matrix
• Wikipedia, Superimposed code

Crossrefs

Cf. A054961, A303977 gives the number of distinct solutions.

Extensions

a(10)-a(11) from Zhao Hui Du, May 04 2018

a(12)-a(13) from Steinar H. Gunderson, Jul 17 2025