[seqfan] Re: Partitioning the n-cube into sets with mutual distance 1

[israel at math.ubc.ca]

For n=6, I get an upper bound of 19 (because a triple can have distance 1 
to at most 18 other subsets), and a lower bound of 18, with e.g.

1: (011110) (110100) (110101) (111011) 
2: (010101) (100110) (101101) (110110) 
3: (000000) (001101) (010000) (111100) 
4: (010100) (101010) (111111) 
5: (001010) (001111) (100100) (110011) 
6: (001100) (101111) (111001) 
7: (000111) (011101) (101110) (110000) 
8: (000011) (010011) (011100) (100101) 
9: (011011) (100011) (111000) (111101) 
10: (001001) (100000) (100111) (111110) 
11: (010010) (011001) (110111) 
12: (000100) (000110) (001011) (011010) 
13: (000001) (101011) (110010) 
14: (000010) (011111) (101001) 
15: (000101) (001000) (010111) (111010) 
16: (001110) (010001) (101000) 
17: (011000) (100010) (110001) 
18: (010110) (100001) (101100) 


Cheers,
Robert

On Aug 10 2016, israel at math.ubc.ca wrote:

>For n=5, I was able to get 11 subsets, e.g.
>
>1: (00011) (11000) (11111) 
>2: (00010) (00100) (00110) 
>3: (00000) (10011) (11110) 
>4: (01010) (10001) (11001) 
>5: (00101) (01000) 
>6: (01101) (10000) (10100) 
>7: (01001) (10010) (10111) 
>8: (01110) (10101) (11100) 
>9: (01011) (01100) (11010) 
>10: (00001) (01111) (10110) 
>11: (00111) (11011) (11101) 
>
>This is optimal.  With a partition of 32 vertices into more than 10 sets,
>at least one of the sets has cardinality at most 2.  Each vertex has
>degree 5, so a set of cardinality <= 2 can have distance 1 to at most 10
>other subsets of the partition.
>
>1,2,3,4,8,11 has 7 hits, none of which look very promising.
>
>Cheers,
>Robert
>
>
>On Aug 10 2016, Neil Sloane wrote:
>
>> Partition the 2^n vertices of the n-cube into M subsets so that the 
>> Hamming distance between any two subsets is exactly 1. What is the max 
>> value of M?
>>
>>According to this paper:
>>
>> Blokhuis, A., Metsch, K., Moorhouse, G. E., Ahlswede, R., & Bezrukov, S. 
>> L. (1993). Partitioning the n-cube into sets with mutual distance 1. 
>> Applied mathematics letters, 6(4), 17-19 (If you look on the web, there 
>> is a copy on ResearchGate), for n=0,1,2,3,4 the answers are M = 
>> 1,2,3,4,8
>>
>>For n=4, here is a solution:
>>0000,1111
>>1000, 0111
>>0100,  1010
>>0010, 1001
>>0001, 1100,
>>0011, 1110
>>0110, 1101
>>0101, 1011
>>
>> There are 169 sequences in the OEIS that match 12348, and the server is 
>> too slow to check them all.
>>
>>Can anyone find a couple more terms?
>>
>>--
>>Seqfan Mailing list - http://list.seqfan.eu/
>>
>>
>