Month: September 2020

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 {G_\ell} which is defined as follows: Vertices are the elements of {\{ 0, 1 \}^{2\ell+1}} and two vertices are adjacent if they have Hamming distance {\ell} or {\ell+1}, that is they differ in {\ell} or {\ell+1} positions. On page 12, they obtain the following bound:

Theorem 1 A clique of {G_\ell} has at most size {2\ell+2}.

Here we will discuss equality in this bound and a small improvement for {\ell} even.