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

israel at math.ubc.ca israel at math.ubc.ca
Wed Aug 10 23:39:31 CEST 2016

```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/
>>
>>
>
```