A361928 -id:A361928 - cp's OEIS frontend

A054961 Maximal number of binary vectors of length n such that the unions (or bitwise ORs) of any 2 distinct vectors are all distinct.

1, 2, 3, 4, 5, 6, 8, 10, 13, 17

Offset: 0

N. J. A. Sloane, May 24 2000

Maximal number of subsets of an n-set such that the unions of any 2 distinct subsets are all distinct.
The concatenation of these vectors produces a 2-separable matrix.
It follows from the Erdős-Frankl-Füredi paper that a(n) grows exponentially with n.
a(9) >= 17. Here is a candidate solution: {011010001 001001010 101000110 100000001 000010110 110010100 010000011 000110000 001001101 010000100 110001000 000101100 100100010 001000000 010100101 111100000 000011001}. - Dmitry Kamenetsky, Jul 17 2017
a(10) >= 22. Here is a candidate solution: {1010110000 1110000000 0010011000 0110100001 1000010101 0011000101 1001000000 0000000010 0001110100 0001001000 0010101010 1100010010 0000010001 0000101101 0100010100 0000011110 0100101000 0001100011 0000100100 0101000001 0101000110 1010000011}. - Dmitry Kamenetsky, Jul 17 2017
a(11) >= 31. Here is a candidate solution: {00101010010 01100101000 00001101100 00001010101 00100110100 00101001001 01000100101 00010101001 10001100001 11010000010 01001001010 00000001111 01111000000 00110010001 10000111000 11100000001 10010000101 00011110000 01000011001 00100100011 01010010100 01000110010 10110100000 10101000100 11001010000 00011000110 10000010011 10000100110 10100001010 00010011010 00000000100}. - Dmitry Kamenetsky, Jul 21 2017
a(12) >= 46. Here is a candidate solution: {011000011000 000000001000 000110100001 111000000010 110100000100 000010110100 010100010010 000011000011 010001001010 000111001000 010000101100 001001100010 100010000110 000001010110 001010101000 010010100010 001001001001 101000100100 000001100101 100011100000 000100011100 001000010011 010100001001 101100001000 100110010000 001110000010 100001001100 010101100000 110001000001 110010001000 011000100001 001100110000 001000001110 000010001101 110000110000 000100100110 000010011010 101001010000 000101010001 001100000101 100000010101 000001111000 101010000001 100101000010 010000000111 010010010001}. - Dmitry Kamenetsky, Jul 21 2017
From Zhao Hui Du, Mar 30 2018: (Start)
Library "Nauty and Traces" is used to filter automorphism graph to verify a(9)=17.
a(13) to a(27) are >= 55,62,70,90,112,140,180,226,279,353,444,558,679,879,1059. (End)
a(13) to a(27) are >= 55,63,72,91,112,145,182,230,281,359,447,566,685,891,1065. - Zhao Hui Du, Apr 19 2018
1.134^n <= a(n) <= ceiling(2^((n+1/2))). The lower bound follows from Theorem 2 of the Erdős-Frankl-Füredi paper and the upper bound is because the union of any two vectors must be unique so a(n)*(a(n)-1)/2 <= 2^n. - Sarosh Adenwalla, May 25 2024

			Solutions for n=4..8:
{0000 0001 0010 0100 1000};
{00000 00001 00010 00100 01000 10000};
{000000 000011 001100 010101 011010 100110 101001 110000};
{0000000 0000011 0000101 0001001 0010010 0100100 0111000 1001000 1010100 1100010};
{00000000 00000011 00001100 00010101 00100110 00111000 01001001 01010010 01100000 10001010 10010000 10100001 11000100}.

Computed by Michael B. Greenwald (mbgreen(AT)central.cis.upenn.edu), Jud McCranie, David W. Wilson, May 24 2000. a(8) >= 13.

Background: D.-Z. Du and F. K. Hwang, Combinatorial Group Testing and Its Applications, World Scientific, 2nd ed., 2000; see Chap. 7.
Asymptotic results: P. Erdos, 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.
Math Stack Exchange, Logic problem: Identifying poisoned wines out of a sample, minimizing test subjects with constraints
Wikipedia, Disjunct Matrix

Cf. A054962 (number of solutions), A304041 (number of distinct solutions), A286874.

Cf. A290492 (3-separable), A361928.

a(8) from Giovanni Resta, Mar 30 2006

a(9) from Zhao Hui Du, Mar 30 2018

A290492 Maximal number of binary vectors of length n such that the unions (or bitwise ORs) of any 3 distinct vectors are all distinct.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14

Offset: 0

Dmitry Kamenetsky, Aug 04 2017

Maximal number of subsets of an n-set such that the unions of any 3 distinct subsets are all distinct.
The concatenation of these vectors produces a 3-separable matrix.
a(13) >= 15. Here is a candidate solution: {1100100010000 0100010000011 0001101000001 0000000011001 1010000100001 0010100001010 0101000101000 0001000000000 0110001000100 0000110000100 0000001100010 1001000000110 0000000110100 0011010010000 1000011001000}. - Dmitry Kamenetsky, Sep 07 2017

			Here is a solution for n=12: {100000001100 000001010001 100101100000 010000110100 000110000101 011100000000 001000101001 000000000000 101010010000 001001000110 000100011010 000010100010 110000000011 010011001000}.

Background: D.-Z. Du and F. K. Hwang, Combinatorial Group Testing and Its Applications, World Scientific, 2nd ed., 2000; see Chap. 7.

Wikipedia, Disjunct Matrix

Cf. A054961, A361928.

cp's OEIS Frontend

A054961 Maximal number of binary vectors of length n such that the unions (or bitwise ORs) of any 2 distinct vectors are all distinct.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions