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.

1. The Inertia Bound

A weighted adjacency matrix of a graph on $ {v}$ vertices is a symmetric $ {v \times v}$ matrix such that $ {A_{xy} = 0}$ whenever $ {x}$ and $ {y}$ are non-adjacent. Let $ {v_+(A)}$ denote the number of positive eigenvalues of $ {A}$ and let $ {v_-(A)}$ denote the number of negative eigenvalues of $ {A}$ (so $ {0}$ eigenvalues are left out). The bound is now as follows (usually attributed to Cvetković’s PhD thesis from 1971, but I do not know if it already contains the weighted version).

Theorem Let $ {X}$ be a graph with weighted adjacency matrix $ {A}$. We have $ {\alpha := \alpha(X) \leq \min\{ v – v_+(A), v – v_-(A) \}}$.

This can be shown very easily by matrix interlacing. Let $ {B}$ the submatrix of $ {A}$ induced by a subgraph. Let $ {\theta_1(A) \geq \ldots \geq \theta_v(A)}$ denote the eigenvalues of $ {A}$ and let $ {\theta_1(B) \geq \ldots \geq \theta_{\alpha}(B)}$ denote the eigenvalues of $ {B}$. The Cauchy’s interlacing theorem says that $ {\theta_{n-s+i}(A) \leq \theta_i(B) \leq \theta_i(A)}$. The induced subgraph on an independent set of $ {A}$ will be an all-zero-matrix, so we have $ {0 \leq \theta_\alpha(A)}$ and, therefore, $ {v_-(A) \leq n-\alpha}$. $ {v_+(A) \leq n-\alpha}$ follows similarly.

The bound itself is very hard to apply as it is very hard to find a suitable $ A$. In general one wants to look for $ A$ in a small matrix algebra and not all possible matrices. For the ratio bound this is the so-called Bose-Mesner algebra which makes applying it very easy. In this context, Terry Tao’s Remark 4 in his post, which discusses exactly this, is very interesting.

2. Godsil’s Conjecture

One of the questions which I learned at the beginning of my PhD and which I considered very intriguing is the following due to Chris Godsil.

Question 1 Exists for all graphs $ {X}$ a weighted adjacency matrix $ {A}$ such that

$ \displaystyle \alpha(X) = \min\{ v – v_+(A), v – v_-(A) \}? $

This looks like a very strong claim, but it turns out that it was not easy to find a counterexample. But first let us look at the evidence in favour of it:

• All 12 million graphs on up to $ {10}$ vertices have such a weight matrix.
• All vertex-transitive graphs on up to $ {12}$ vertices have such a weight matrix.
• All perfect graphs have such a weight matrix.
• Many families of strongly regular graphs have such a weight matrix.
• Many families of Cayley graphs have such a weight matrix.

So it seems that the answer to the question should be “no”, but it is not at all easy to find a counterexample. This happened only in 2016 due to work by John Sinkovic.

3. The Counterexample on $ {17}$ Vertices

A basic tool to Sinkovic’s result is the following (you can see that the $ {\alpha+1}$ part reminds me of Huang’s result):

Lemma If $ {A}$ has a principle submatrix with $ {\alpha+1}$ positive eigenvalues and a principle submatrix with $ {\alpha+1}$ negative eigenvalues, then $ {\alpha < \min\{ v – v_+(A), v – v_-(A) \}}$.

The proof is easy. With the same argument as before, interlacing implies that $ {A}$ satisfies $ {v_-(A) \leq v-(A)-\alpha-1}$ (and the analogous for $ {v_+(A)}$). Then the inertia bound cannot be tight. The tricky part is, and that is were all the work was for Sinkovic, is to show that no such matrix $ {A}$ exists for a particular graph.

The graph that works is the Paley graph $ {P(17)}$. That is the graph on $ {17}$ vertices with the elements of $ {\mathbb{F}_{17}}$ as its vertices and two vertices are adjacent if their difference is a (nonzero) square of $ {\mathbb{F}_{17}}$. It is known that $ {\alpha(P(17)) = 3}$, so one needs to find a principle submatrix with at least $ {4}$ positive (resp. negative) eigenvalues. The main (and hardest) part of the argument is to look at a certain subgraph of $ {P(17)}$ and show that the induced submatrix always has 4 negative (positive) eigenvalues. This I will not discuss here.

Sinkovic also observed that one can delete one vertex, so the smallest graph for which the inertia bound is not tight, has $ {16}$ vertices.

So we can modify Godsil’s question in an obvious way:

Question 2 Exists for all but finitely many graphs $ {X}$ a weighted adjacency matrix $ {A}$ such that

$ \displaystyle \alpha(X) = \min\{ v – v_+(A), v – v_-(A) \}? $

Question 3 Exists for almost all graphs $ {X}$ a weighted adjacency matrix $ {A}$ such that

$ \displaystyle \alpha(X) = \min\{ v – v_+(A), v – v_-(A) \}? $

Again, the answer should be no for both of the questions, but it is not clear how to show this. Sinkovic’s proof heavily relied on the fact that there are only 17 vertices. Interestingly, this alone is not even enough as the question is (to my knowledge) open for the smaller Paley graph $ P(13)$.