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.

1. Equality for ${\ell}$ odd

Yu, Nathan and Levent use a version of the ratio bound, so the proof is very nice. They also mention that the bound is tight as we can take a ${(2\ell+2)\times (2\ell+2)}$ Hadamard matrix and remove one column. Here an example for ${\ell=1}$. This is the corresponding Hadamard matrix:

$\displaystyle \begin{pmatrix} 1 & 1 & 1 & 1\\ 1 & 1 & -1 & -1\\ 1 & -1 & 1 & -1\\ 1 & -1 & -1 & 1 \end{pmatrix}$

Our graph has ${0}$s and ${1}$s, so let’s replace ${-1}$s by ${0}$s and chop the last column:

$\displaystyle \begin{pmatrix} 1 & 1 & 1\\ 1 & 1 & 0\\ 1 & 0 & 1\\ 1 & 0 & 0 \end{pmatrix}$

The rows above correspond to ${2\ell+2 = 4}$ vertices pairwise at distance ${1}$ or ${2}$. As Hadamard matrices of size ${2\ell+2}$, where ${2\ell+2 \geq 4}$, only exist if ${4}$ divides ${2\ell+2}$, we have that ${\ell}$ is odd for all examples obtained this way.

2. A Small Improvement

Now the small improvement for ${\ell}$ even.

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

This is probably somewhere in literature, but I would like to know where (this was Nathan’s question to me). And I would also like to know if there is a construction to obtain equality in this bound. Using Hadamard matrices, but this time adding a column to them, it is easy to see that the existence of a Hadamard matrix of size ${2\ell}$ implies the existence of a clique of size ${2\ell}$ in ${G_\ell}$.

So how do we prove this better bound? We use a method from an old blog post of mine here. We will first do this for ${\ell=2}$. Let’s say that ${A_j}$ is the adjacency matrix of the distance-${j}$ graph on ${\{ 0, 1\}^5}$. That is ${(A_j)_{xy}}$ is ${1}$ if ${x}$ and ${y}$ have Hamming distance ${j}$, and ${0}$ otherwise. The eigenvalues of these graphs are well-known. Here, the ${j}$th column corresponds to the eigenvalue of the ${j}$th graph (${j = 0, 1, 2, 3, 4, 5}$):

$\displaystyle P := \begin{pmatrix} 1 & 5 & 10 & 10 & 5 & 1\\ 1 & 3 & 2 & -2 & -3 & -1\\ 1 & 1 & -2 & -2 & 1 & 1\\ 1 & -1 & -2 & 2 & 1 & -1\\ 1 & -3 & 2 & 2 & -3 & 1\\ 1 & -5 & 10 & -10 & 5 & -1 \end{pmatrix}$

It is noteworthy that the rows are not random. These ${6}$ graphs share their eigenspaces ${V_0, V_1, \ldots, V_5}$, a common property of distance-regular graphs and, more generally, association schemes. A reason for those who want to know: The ${A_j}$‘s commute, so we can diagonalize them simultaneously. Another well-known and very nice thing about this set of graphs is that the eigenvalue matrix ${P}$ also provides you with an explicit orthogonal projection matrix onto the eigenspace ${V_i}$. Define the projection matrix ${E_i}$ by ${2^5 \cdot (E_i)_{xy} = P_{ji}}$ if ${x}$ and ${y}$ have Hamming distance ${j}$. And we also know that the dimension of ${V_i}$ is equal to ${P_{0i}}$.

To show the theorem for ${\ell=2}$, we look at ${E_4}$. We do know that ${\text{rank}(E_4) = \text{dim}(V_4) = 5}$. If ${Y}$ is a clique of ${G_2}$, then we also know that the submatrix ${E'}$ of ${E_4}$ index by ${Y}$ is of the form ${2^{-5} (5I + (J-I))}$. Clearly, this matrix has full rank, hence ${|Y| = \text{rank}(E') \leq \text{rank}(E_4)}$. Hence, ${|Y| \leq 5}$ as claimed.

Now let’s do the same in general with ${n=2\ell+1}$. We still have ${2^{-n} (E_i)_{xy} = P_{ji}}$ for ${x}$ and ${y}$ at distance ${j}$ and ${\dim(V_i) = P_{0i}}$. The entries of ${P}$, given by the Krawtchouk polynomials, are

$\displaystyle P_{ij} = \sum_{h=0}^j (-1)^h \binom{i}{h} \binom{n-i}{j-h}.$

We only care about ${P_{ji}}$ with ${i=n-1}$. In this case, the formula simplifies to

$\displaystyle P_{j,n-1} = \sum_{h=0}^{n-1} (-1)^h \binom{j}{h} \binom{n-j}{n-1-h} = (-1)^{j-1} j + (-1)^j (n-j) = (-1)^j (n-2j).$

In fact, we only case about ${j=0,\ell,\ell+1}$. We obtain ${P_{0,2\ell} = n}$, and ${P_{\ell,2\ell} = (-1)^\ell = P_{\ell+1,2\ell}}$. Hence, the submatrix ${E'}$ of ${E_{2\ell}}$ indexed by ${Y}$ is a multiple of ${nI + (-1)^\ell (J-I)}$, so it has full rank if ${\ell}$ is even. Hence, ${|Y| = \text{rank}(E')}$. But ${\text{rank}(E') \leq \text{rank}(E) = 2\ell+1}$. Therefore, ${|Y| \leq 2\ell+1}$.

We also obtain an alternative proof for ${|Y| \leq 2\ell+2}$ for ${\ell}$ odd. Indeed, ${nI - (J-I)}$ has rank ${|Y|-1}$ if ${|Y| = 2\ell+2}$. Hence, the bound is worse by one in this case.

3. Equality for ${\ell}$ even

As the authors of the preprint mention, ${G_2}$ has clique number ${5 = 2\ell+1}$. Here is an example for equality:

11110
11001
10101
10011
01111

This is a Hadamard matrix of size ${4}$ with one column and row added. As mentioned before, I would be curious to know if one can do this more generally.

Acknowledgements My thanks go to Nathan Lindzey for having a look at a draft of this article.