# Month: September 2020

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.