[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:19:49 CEST 2016


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


More information about the SeqFan mailing list