hypercube

Six Spectral Bounds

I spent the last few days in vain using several spectral arguments to bound the size of certain intersection problems. For instance what is the largest set of vectors in {\{ 0, 1 \}^4} pairwise at Hamming distance at most {2} (a problem solved by Kleitman, recently investigated by Huang, Klurman and Pohoata). Here the answer is {5} and {0000}, {0001}, {0010}, {0100}, {1000} would be such an example. Or the largest set of vectors in {\{ 0, 1 \}^7} pairwise at distance {2} or {6}. Here the answer is {8} and an example is {0000001}, {0000010}, {0000100}, {0001000}, {0010000}, {0100000}, {1000000}, {1111111}. This is a problem which I recently investigated together with Hajime Tanaka, extending work by Frankl and others.

Usually, this playing around does not lead to anything. But this time …. It is actually the same. However, I did one useful thing which is the following: Generously counting, I do know five different easy spectral arguments which can be used to investigate these questions. This blog post presents these methods for the two problems mentioned above.
(more…)