[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