# rank bound

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.

# Huang’s Breakthrough, Cvetković’s Bound, Godsil’s Question, and Sinkovic’s Answer

Let us consider the ${n}$-dimensional hypercube ${\{ 0, 1 \}^n}$. The Hamming graph on ${H_n}$ has the elements of ${\{ 0, 1 \}^n}$ as vertices an two vertices are adjacent if their Hamming distance is one, so they differ in one coordinate. It is easy to see that the independence number ${\alpha}$ of this graph is ${2^{n-1}}$.

It was a long open and famous problem what the maximum degree of an induced subgraph on ${H_n}$ with ${\alpha+1}$ vertices is. Very recently, Hao Huang showed that the answer is “at least ${\sqrt{n}}$” and everyone is blogging about it (only a small selection): Anurag Bishnoi, Gil Kalai, Terry Tao, Fedya Petrov. Here I am jumping on this bandwagon.

Huang uses a variant of the inertia bound (or Cvetković bound). It is a good friend of the ratio bound (or Hoffman’s bound) which is the namesake of this blog. For the second time this year (the first time was due to a discussion with Aida Abiad), this I was reminded me of a result by John Sinkovic from 3 years ago. This blog posts is about Sinkovic’s result which answered a question by Chris Godsil on the inertia bound.
(more…)