# 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…)