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

Neil Sloane njasloane at gmail.com
Thu Aug 11 04:00:31 CEST 2016


Robert, Thanks for the updates. I created https://oeis.org/A275646 for
the problem.  I have also written to Aart Blokhuis about their old paper.

Best regards
Neil

Neil J. A. Sloane, President, OEIS Foundation.
11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
Phone: 732 828 6098; home page: http://NeilSloane.com
Email: njasloane at gmail.com


On Wed, Aug 10, 2016 at 5:39 PM, <israel at math.ubc.ca> wrote:

> 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/
>>>
>>>
>>>
>>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>


More information about the SeqFan mailing list