Eigenvalues of the Kneser graph

Wildon's Weblog 2023-06-09

On Tuesday Ehud Friedgut gave a beautiful talk in the Bristol Combinatorics Seminar, titled ‘The most complicated proof ever of Mantel’s theorem, and other applications of the representation theory of the symmetric group’, based on joint work with Yuval Filmus, Nathan Lindzey and Yuval Wigderson. As the title promised, he used the representation theory of the symmetric group to prove Mantel’s Theorem, that if a graph on $2m$ vertices has more edges than the complete bipartite graph with bipartition into two parts of size $m$ then it contains a triangle. He illustrated the method by instead proving the Erdős–Ko–Rado Theorem, that the maximum size of a family of $r$ -subsets of $\{1,\ldots, n\}$ such that any two members of the family have a non-trivial intersection is $\binom{n-1}{r-1}$ . The purpose of this post is to outline the new proof (as I understand it from Ehud’s talk) of this result, dropping in my own proof of one of the lemmas he used. At the end I’ll record a possible generalization/variation I raised at the end of the talk. Let me emphasise that — apart from the minor proof of the lemma, which in any case uses results of James — no originality is claimed for anything in this post.

A graph for the Erdős–Ko–Rado Theorem

The graph $G$ we need to prove the Erdős–Ko–Rado Theorem is the Kneser graph, having as its vertices the $r$ -subsets of $\{1,\ldots, n\}$ . Two subsets $X$ and $Y$ are connected by an edge if and only if $X \cap Y = \varnothing$ . The Erdős–Ko–Rado Theorem is then the claim that the maximum size of an independent set in $G$ is $\binom{n-1}{r-1}$ . As we shall see below, this follows from the Hoffman bound, that an independent set in a $d$ -regular graph on $N$ vertices with adjacent matrix $A$ and least eigenvalue $-\lambda$ has size at most $N \lambda / (d+\lambda)$ . (Note that since the sum of the eigenvalues is the trace of the adjacency matrix, namely $0$ , and the largest eigenvalue is the degree $d$ , the least eigenvalue is certainly negative.)

Representations

To find the eigenvalues of $A$ , Ehud and his coauthors use the representation theory of the symmetric group. Let $V$ be the permutation module of $S_n$ acting on the $r$ -subsets of $\{1,\ldots, n\}$ . It is well known that $V$ has character

$\chi^{(n)} + \chi^{(n-1,1)} + \cdots + \chi^{(n-r,r)}.$

Since this character is multiplicity-free, there is a unique direct sum decomposition of $V$ into Specht modules,

$V = S^{(n)} \oplus S^{(n-1,1)} \oplus \cdots \oplus S^{(n-r,r)}. \quad (\star)$

The adjacent matrix $A$ acts as a linear map on $V$ that commutes with the $G$ -action. Therefore, by Schur’s Lemma, for each $s$ with $0\le s \le r$ there is a scalar $\lambda(s)$ such that $A$ acts on $S^{(n-s,s)}$ as multiplication by $\lambda(s)$ . Thus the $\lambda(s)$ are the eigenvalues (possibly with repetition, but this turns out not to be the case) of $A$ .

Lemma. The adjacency matrix $A$ acts on $S^{(n-s,s)}$ by scalar multiplication by $(-1)^s\binom{n-r-s}{r-s}$ .

Proof. It follows from the theory in Chapter 17 of James’ Springer lecture notes on the symmetric groups that $V$ has a filtration

$V = V_0 \supset V_1 \supset \ldots \supset V_r \supset 0$

such that $V_r \cong S^{(n-r,r)}$ and $V_s / V_{s+1} \cong S^{(n-s,s)}$ for $0\le s < r$ . The submodule $V_r$ is spanned by certain ‘partially symmetrized’ polytabloids. Rather than introduce this notation, which is a bit awkward for a blog post, let me instead suppose that $S_n$ acts on the set $\{1,\ldots, s, \overline{1}, \ldots, \overline{s}\} \cup Z$ where $|Z| = n-2s$ . Let $X$ be a fixed $(s-r)$ -subset of $Z$ . Then $V_s$ is a cyclic $\mathbb{C}S_n$ -module generated (using right modules) by $v(s)$ where

$v(s) = \bigl( \{1,\ldots, s\} \cup X\bigr) \bigl(1-(1,\overline{1})\bigr) \ldots \bigl( 1- (s,\overline{s}) \bigr)$

There is a ‘raising map’ $R : V_s \rightarrow S^{(n-s,s)}$ which — viewing $S^{(n-s,s)}$ as a submodule of the permutation module of $S_n$ acting on $s$ -subsets — is defined on the generator $v(s)$ by

$v(s) \mapsto \{1,\ldots, s\} \bigl(1-(1,\overline{1})\bigr) \ldots \bigl( 1- (s,\overline{s}) \bigr)$

Applying the adjacency matrix $A$ sends an $r$ -subset to all those $r$ -subsets that it does not meet. Hence if we first apply $A$ then $R$ to $v(s)$ then, in order to get a scalar multiple of $v(s)A$ , we must pick an $r$ -subset not meeting $\{1,\ldots, s\} \cup X$ that contains $\{\overline{1}, \ldots, \overline{s}\}$ , i.e. an $r$ -subset of the form

$\{\overline{1},\ldots, \overline{s}\} \cup Y$

where $Y$ is an $(r-s)$ -subset of $Z \backslash X$ . Since $|Z \backslash X| = (n-2s) - (r-s) = n-r-s$ , there are $\binom{n-r-s}{r-s}$ possible choices. Each comes with sign $(-1)^s$ . $\Box$

End of proof

The lemma implies that $\lambda(1) = -\binom{n-r-1}{r-1}$ is the least eigenvalue of $A$ . Putting this into Hoffman’s bound and using that the graph $G$ is regular of degree $\binom{n-r}{r}$ , since this is the number of $r$ -subsets of $\{1,\ldots, n\}$ not meeting $\{1,\ldots, r\}$ , we get that the maximum size of an independent set is at most

$\displaystyle \frac{\binom{n}{r} \binom{n-r-1}{r-1}}{\binom{n}{r}-\binom{n-r}{r} + \binom{n-r-1}{r-1}} = \frac{\binom{n-r-1}{r-1}}{1 - \binom{n-r}{r-1}/\binom{n}{r}}$

which is just a shade more than $\binom{n-r-1}{r-1}$ . Thus we (or rather Ehud and his coauthors) have proved the Erdős–Ko–Rado Theorem for $n$ sufficiently large. Ehud mentioned that it was legitimate to apply the Hoffman bound to a scaled adjacency matrix, and by choosing a clever scaling, one could get the theorem on the nose. He then went on to outline how the method applies to Mantel’s Theorem: the relevant representation is, in the usual notation, $M^{(n-3,2,1)}$ ; note one may interpret an $(n-3,2,1)$ -tabloid as an ordered pair $\bigl( \{i, j\}, \{k \} \bigr)$ encoding the path of length 3 with edges $\{i,k\}$ and $\{j,k\}$ . There is a proof of Mantel’s Theorem by double counting using these paths: as Ehud remarked (quoting, if I heard him right, Kalai) ‘It’s very hard not to prove Mantel’s Theorem’.

Possible variations

I’ll end with two possible avenues for generalization, both motivated by the classification of multiplicity-free permutation characters of symmetric groups. My paper built on work of Saxl and was published at about the same time as parallel work of Godsil and Meagher.

Foulkes module

The symmetric group $S_{2m}$ acts on the set of set partitions of $\{1,\ldots, 2m\}$ into $m$ sets each of size $2$ . The corresponding permutation character is multiplicity free: it has the attractive decomposition $\sum_{\lambda \in \mathrm{Par}(n)} \chi^{2\lambda}$ , where $2\lambda$ is the partition obtained from $\lambda$ by doubling the length of each path. Moreover, my collaborator Rowena Paget has given an explicit Specht filtration of the corresponding permutation module, analogous to the filtration used above of $M^{(n-r,r)}$ . So everything is in place to prove a version of the Erdős–Ko–Rado Theorem for perfect matchings.

Finite general linear groups

There is a remarkably close connection between the representations of $S_n$ and the unipotent representations of the finite general linear group $\mathrm{GL}_n(\mathbb{F}_q)$ , which perhaps will, one day, be explained by defining the symmetric group as a group of automorphisms of a vector space over the field with one element. Coming down to earth, the analogue of the permutation module $M^{(n-r,r)}$ of $S_n$ acting on $r$ -subsets is the permutation module of $\mathrm{GL}_n(\mathbb{F}_q)$ acting on $r$ -subspaces of $\mathbb{F}_q^n$ . This decomposes as a direct sum of irreducible submodules exactly as in $(\star)$ above, replacing the Specht modules with their $\mathrm{GL}_n(\mathbb{F}_q)$ -analogues. So once again the decomposition is multiplicity-free. This suggests there might be a linear analogue of the Erdős–Ko–Rado Theorem in which we aim to maximize the size of a family of subspaces of $\mathbb{F}_q^n$ such that any two subspaces have at least a $1$ -dimensional intersection.

A Putnam problem

The second suggested generalization might tie in with another project I’ve worked on but neglected to write up beyond a blog post: to prove the $\mathrm{GL}_n(\mathbb{F}_q)$ -analogue of the spectral results on the Kneser graph motivated by Problem A2 in the 2018 Putnam.