In a recent breakthrough Hao Huang proved the sensitivity conjecture, that had remained open for past 30 years despite some serious effort from various computer scientists and mathematicians. The proof can be described in a single tweet (if you have the basic background), and it has appeared on the ELI5 page of reddit. The main ideas behind the proof are from spectral graph theory, and one of the starting points (see for example this comment) is the following bound on the independence number of a graph due to Cvetković:
Lemma 1 (Inertia Bound). Let be a graph on vertices and let be its eigenvalues. Let be the number of non-negative eigenvalues of , and the number of non-positive eigenvalues (counted with multiplicity). Then .
The proof of this Lemma is a nice application of a classical result in mathematics known as Cauchy’s interlacing theorem (I have talked about eigenvalue interlacing earlier in this blog), and I leave it to the reader to fill in the details*. This spectral upper bound on the independence number of a graph is relatively less known than Hoffman/Delsarte bound which says . Since many combinatorial problems can be rephrased as finding a nice upper bound on the independence number of some graph, such spectral results can be quite useful, when one has enough structure to say something about the eigenvalues. Until recently, I didn’t see any applications of the inertia bound in extremal combinatorics, whereas Hoffman’s bound is widely used; for example, in proving Erdős-Ko-Rado theorems. Interestingly, the classical Erdős-Ko-Rado theorem can also be proved using the Lemma 1 (as I learned from Hao Huang’s talk at our combinatorics seminar).
One interesting observation made by Huang regarding Lemma 1 (which was already known) is that instead of using the eigenvalues of the adjacency matrix of the graph, we could use any pseudo-adjacency matrix and still arrive at the same conclusion. A pseudo-adjacency matrix of a graph on vertices is any real symmetrix matrix with the property that whenever the -th vertex is non-adjacent to the -th vertex (in an adjacency matrix we also require for every adjacent pair). If are the number non-negative/positive eigenvalues of , then from the proof of Lemma 1 using interlacing we again get .
The flexibility of using the pseudo-adjacency matrix is crucial to Huang’s breakthrough result. In fact, before the proof of the sensitivity conjecture, Huang (in collaboration with Oleksiy Klurman and Cosmin Pohoata) used the same method to give a spectral proof of another theorem on the hypercube, known as Kleitman’s theorem, which is what I want to discuss in this blog post. In particular, I want to give a slightly simplified proof due to Aditya Potukuchi and Amey Bhangale, that my friend Aditya shared with me a few days after Huang’s sensitivity paper appeared on arXiv as an application of his methods, without realising that a spectral proof of this theorem had already appeared in an earlier paper of Huang. Here is the theorem that we will prove:
Theorem 2 (Kleitman). Let be a set of vectors in such that the hamming distance between any two vectors in is at most . Then
(This can be seen as the discrete analog of the isodiametric theorems in real geometry where one wants to find the largest volume of a set of points with a given diameter.)
To use Lemma 1 above, we will naturally consider the graph on where two vectors are adjacent if the hamming distance between them is at least , because then any independent set in this graph corresponds to such a set in the theorem. What are the eigenvalues of the graph ?
The boolean hypercube, , and the graphs defined on it using hamming distance are well studied objects. One way of computing the eigenvalues of is to look at it as the Cayley graph Cay, where is the Hamming ball of radius , that is, all vectors whose Hamming weight is at most . From the basic theory of Cayley graphs, it then follows that has distinct eigenvalues with
appearing with multiplicity , where is the Kravchuk polynomial evaluated at , defined as
Note that is a polynomial of degree . For ease of notation, we will skip the superscript from now on and just write instead. These polynomials have several nice properties, and we will use the following symmetry (or should it be called anti-symmetry?):
which lets us see the evaluation of a degree polynomial at as the evaluation of a degree polynomial at , up-to a factor of . This fact will come in handy later.
Now if you apply Lemma 1 to using these eigenvalues, you will realise (after some calculation) that it does not give the required bound (what bounds do you get?). That’s where pseudo-adjacency matrices come into picture. We will define a weight function , such that every vector with non-zero values is given the weight , and for all . From this weight function we will get the pseudo-adjacency matrix of where if the Hamming distance between the -th and the -th vectors is equal to . Again, from the basic theory of Cayley graphs (in particular, calculating Fourier coefficients), or more directly (Lemma 2.3 here), we get that has distinct eigenvalues,
with multiplicity , with . Now, we just have to choose the function cleverly so that either , or , is at most what we need it to be. Here is when Huang, Klurman and Pohoata make the clever choice of , for the case of . For the odd case, , there is a different choice, but from now on we will only stick to the even case of Theorem 2. From this choice, they get the following three properties,
- , for
- , for
from which the result then follows by an easy analysis. The way they prove these properties is using generating functionology, and it is not immediately clear how the choice of came about. What Aditya and Amey do instead, is start with the properties that one wants from the eigenvalues, and then show the existence of the function , without ever computing it explicitly!
Here is how this is done. Observe that using the symmetric property of Kravchuk polynomials, we can write
In the second formulation, we can see as multiplied with a linear combination of polynomials of degrees , evaluated at . These polynomials are in fact linearly independent, and hence any polynomial of degree at most can be written as a linear combination of them. Therefore, we can choose a nice , for which the eigenvalues will be , and then get the weights ‘s automatically.
Pick as the unique monic polynomial whose roots are , for to . WLOG, assume that (if not, then we can take ). Since is a polynomial, the sign of its values oscillates between the roots. In particular, this shows that has the same sign for , that is, if is odd (since and have the same sign), and if is even, for all of these ‘s. In the former case, we can carefully count the number of negative eigenvalues with multiplicities, and in the latter case we can count the number of positive eigenvalues with multiplicities, giving us Theorem 2.
Note that as far as the signs of ‘s are concerned, this trick of picking the polynomial explicitly, and then getting the weights, gives us the same three properties as we had earlier where Huang, Klurman and Pohoata made the explicit choice of the weight function. For the case of Theorem 2 when , we have to do something different, and I leave it to the reader to figure that case out.
For some open questions that can potentially be solved using these methods, check out Section 5 of the Huang-Klurman-Pohoata paper.
(*) Fedor Petrov has given a “low-level” proof that avoids using the interlacing theorem (congrats to Fedya for his new blog!).