login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A275646 a(n) = maximal value of M such that it is possible to partition the 2^n vertices of the n-cube into M subsets so that the Hamming distance between any two subsets is exactly 1. 1
1, 2, 3, 4, 8, 11 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,2
COMMENTS
a(6) is either 18 or 19 (see Examples below).
REFERENCES
Blokhuis, A., Metsch, K., Moorhouse, G. E., Ahlswede, R., & Bezrukov, S. L., Partitioning the n-cube into sets with mutual distance 1. Applied Mathematics Letters, 6(4) (1993), 17-19.
LINKS
Blokhuis, A., Metsch, K., Moorhouse, G. E., Ahlswede, R., & Bezrukov, S. L., Partitioning the n-cube into sets with mutual distance 1, Applied Mathematics Letters, 6(4) (1993), 17-19. [Annotated scanned copy]
EXAMPLE
a(4) = 8: {0000,1111}, {1000,0111}, {0100,1010}, {0010,1001}, {0001,1100}, {0011,1110}, {0110,1101}, {0101,1011} [Blokhuis et al.]
Comment from Robert Israel, Aug 10, 2016 (Start): 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. Hence a(5) = 11.
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)
So a(6) = 18 or 19.
(End)
CROSSREFS
Sequence in context: A114854 A127279 A106131 * A279194 A050727 A295323
KEYWORD
nonn,more
AUTHOR
N. J. A. Sloane, Aug 10 2016
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 08:22 EDT 2024. Contains 371236 sequences. (Running on oeis4.)