Almost a Hadamard Matrix

Recently, Yu Hin Au, Nathan Lindzey, and Levent Tunçel published a preprint with various spectral bounds on the arXiv. They investigate generalizations of bounds due to Delsarte and Hoffman in the context of the Lovász-Schrijver SDP. Page 12 of that article I knew for a few more days because Nathan asked me if their bound is known. The bound is simply an example to showcase their techniques. Here I will present another method of showing the same bound. Consider the graph which is defined as follows: Vertices are the elements of and two vertices are adjacent if they have Hamming distance or , that is they differ in or positions. On page 12, they obtain the following bound:

Theorem 1 A clique of has at most size .

Here we will discuss equality in this bound and a small improvement for even.

Advertisement