Let us consider the -dimensional hypercube . The Hamming graph on has the elements of 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 of this graph is .

It was a long open and famous problem what the maximum degree of an induced subgraph on with vertices is. Very recently, Hao Huang showed that the answer is “at least ” 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…)