|
%I #76 Jun 03 2018 16:48:53
%S 1,2,3,4,5,6,8,10,13,17
%N Maximal number of binary vectors of length n such that the unions (or bitwise ORs) of any 2 distinct vectors are all distinct.
%C Maximal number of subsets of an n-set such that the unions of any 2 distinct subsets are all distinct.
%C The concatenation of these vectors produces a 2-separable matrix.
%C It follows from the Erdős-Frankl-Furedi paper that a(n) grows exponentially with n.
%C 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
%C 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
%C 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
%C 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
%C From _Zhao Hui Du_, Mar 30 2018: (Start)
%C Library "Nauty and Traces" is used to filter automorphism graph to verify a(9)=17.
%C a(13) to a(27) are >= 55,62,70,90,112,140,180,226,279,353,444,558,679,879,1059. (End)
%C 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
%D Computed by Michael B. Greenwald (mbgreen(AT)central.cis.upenn.edu), _Jud McCranie_, _David W. Wilson_, May 24 2000. a(8) >= 13.
%H Background: D.-Z. Du and F. K. Hwang, <a href="https://www.worldscientific.com/worldscibooks/10.1142/4252">Combinatorial Group Testing and Its Applications</a>, World Scientific, 2nd ed., 2000; see Chap. 7.
%H Asymptotic results: P. Erdos, P. Frankl and Z. Furedi, <a href="https://doi.org/10.1016/0097-3165(82)90004-8">Families of finite sets in which no set is covered by the union of two others</a>, J. Combin. Theory, A33 (1982), 158-166.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Disjunct_matrix">Disjunct Matrix</a>
%e Solutions for n=4..8:
%e {0000 0001 0010 0100 1000};
%e {00000 00001 00010 00100 01000 10000};
%e {000000 000011 001100 010101 011010 100110 101001 110000};
%e {0000000 0000011 0000101 0001001 0010010 0100100 0111000 1001000 1010100 1100010};
%e {00000000 00000011 00001100 00010101 00100110 00111000 01001001 01010010 01100000 10001010 10010000 10100001 11000100}.
%Y Cf. A054962 (number of solutions), A304041 (number of distinct solutions), A286874.
%K nonn,hard,more,nice
%O 0,2
%A _N. J. A. Sloane_, May 24 2000
%E a(8) from _Giovanni Resta_, Mar 30 2006
%E a(9) from _Zhao Hui Du_, Mar 30 2018
| 