rank bound

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.


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.