Month: July 2019

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