Eigenvalues of the Kneser graph

A few days ago 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‘ and 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 first 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. 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 part. I then show that the methods appear (modulo the proof of the claim below) to adapt to proof the analogue of the Erdős–Ko–Rado Theorem for vector spaces.

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, -1, \ldots, -s\} \cup Z$ where $|Z| = n-2s$ . Let $X$ be a fixed $(r-s)$ -subset of $Z$ . Then $V_s$ is a cyclic $\mathbb{C}S_n$ -submodule of $V$ generated (using right modules) by $v(s)$ where

$v(s) = \bigl( \{1,\ldots, s\} \cup X\bigr) \bigl(1-(1,-1)\bigr) \ldots \bigl( 1- (s,-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,-1)\bigr) \ldots \bigl( 1- (s,-s) \bigr)$

Fix an $r$ -set $\{\pm 1, \ldots, \pm s\} \cup X$ appearing in the expansion of $v(s)$ in the canonical basis of $V$ . Applying the adjacency matrix $A$ sends this $r$ -set to all those $r$ -sets that it does not meet. Hence, after applying $A$ and then $R$ we get a scalar multiple of $v(s)$ precisely from those sets $\{\mp 1, \ldots, \mp s\} \cup Y$ in the support of

$\bigl( \{\pm 1, \ldots, \pm s\} \cup X \bigr) A$

such that $Y$ is an $(r-s)$ -subset of $\{1,\ldots, n\}$ not meeting

$\{1,\ldots, s,-1,\ldots, -s\} \cup X.$

There are $2s + (r-s) = r+s$ forbidden elements, hence there are $\binom{n-(r+s)}{r-s}$ choices for $Y$ . 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

$\begin{aligned} \frac{\binom{n}{r} \binom{n-r-1}{r-1}}{\binom{n-r}{r} + \binom{n-r-1}{r-1}}&= \frac{ \binom{n}{r}}{ \binom{n-r}{r}/\binom{n-r-1}{r-1} + 1} \\ &= \frac{ \binom{n}{r}}{ \frac{n-r}{r} + 1} \\ &= \textstyle \binom{n}{r} \frac{r}{n} \\&= \textstyle \binom{n-1}{r-1} \end{aligned}$

which is exactly the Erdős–Ko–Rado bound. Thus we (or rather Ehud Friedgut and his coauthors) have proved the Erdős–Ko–Rado Theorem. Ehud 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. Update. I am grateful to Ehud for pointing out that this has already been done (using slightly different methods) by his coauthor Nathan Lindzey.

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)$ . Perhaps, one day, this will be explained by defining the symmetric group as a group of automorphisms of a vector space over the field with one element. 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 well 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.

Update. The Erdős–Ko–Rado Theorem for vector spaces was proved
in an aptly named paper by Frankl and Wilson in the general version for $t$ -intersecting families. The special case $t=1$ is that the maximum number of $r$ -dimenional subspaces of $\mathbb{F}_q^n$ such that any two subspaces have at least a $1$ -dimensional interection is $\binom{n-1}{r-1}_q$ for $n \ge 2r$ , where the $q$ -binomial coefficient is the number of $r-1$ -dimensional subspaces of $\mathbb{F}_q^{n-1}$ . Thus the maximum is attained by taking all the subspaces containing a fixed line, in precise analogy with the case for sets. (Note also that if $n \le 2r-1$ then any two $r$ -dimensional subspaces have a non-zero intersection.)

James wrote a second set of lecture notes Representation of the general linear groups, pointing out several times the remarkable analogy with the representation theory of the symmetric group. At the time he wrote, before his work with Dipper on Hecke algebras, this seemed somewhat mysterious. (Very roughly, $FS_n$ is to $\mathrm{GL}_d(F)$ where $F$ is an infinite field as the Hecke algebra $\mathcal{H}_q(S_n)$ is to $\mathrm{GL}_d(\mathbb{F}_q)$ .) Chapter 13 of his book has, I think, exactly what we need to prove the analogue of the lemma above. Update: I also just noticed that Section 8.6 of Harmonic analysis on finite groups by Ceccherini-Silberstein, Scarabotti and Tolli, titled ‘The $q$ -Johnson scheme’ is entirely devoted to the Gelfand pair $(\mathrm{GL}_d(\mathbb{F}_q), H_e)$ where $H_e$ is the maximal parabolic subgroup stabilising a chosen $e$ -dimensional subspace.

Here is the setting for the general linear group. Fix $r \le n/2$ and let $M^{(r)}$ be the permutation module of $\mathrm{GL}_n(\mathbb{F}_q)$ acting on $r$ -dimensional subspaces of $\mathbb{F}_q^n$ defined over the complex numbers. For $0 \le s < r$ , let $\psi_s : M^{(r)} \rightarrow M^{(s)}$ be the map sending a subspace to the formal linear combination of all $s$ -dimensional subspaces that it contains. The $\mathrm{GL}_d(q)$ -Specht module $S^{(n-r,r)}$ is then the intersection of the kernels of all the $\psi_s$ for $s < r$ . Moreover if we set

$\displaystyle M_s = \bigcap_{i=0}^{s-1} \ker \psi_i \subseteq M^{(r)}$

then $M^{(r)} = M_0 \supset M_1 \supset \cdots \supset M_r$ and $M_r \cong S^{(n-r,r)}$ and $M_s / M_{s+1} \cong S^{(n-s,s)}$ for $0 \le s < r$ .

The relevant graph, again denoted $G$ has vertices all $r$ -dimensional subspaces of $\mathbb{F}_q^n$ ; two subspaces are adjacent if and only if their intersection is $\{0\}$ .

Lemma. The degree of $G$ is $\binom{n-r}{r}_q q^{r^2}$ .

Proof. Fix a basis $e_1, \ldots, e_n$ for $\mathbb{F}_q^n$ and let $t \le n-r$ . An arbitrary $t$ -dimensional subspace of $\mathbb{F}_q^n$ intersecting $\langle e_1, \ldots, e_r\rangle$ in $\{0\}$ has the form

$\langle v_1 + e_{i_1}, \ldots, v_t + e_{i_t} \rangle$

where $r+1 \le i_1 < \ldots < i_t \le n$ and

$v_1, \ldots, v_t \in \langle e_1, \ldots, e_r \rangle.$

These choices of 'pivot columns' and matrix coefficients uniquely determine the subspace. Hence there are $q^{rt} \binom{n-r}{t}$ such subspaces. Taking $t = r$ we get the result. $\Box$

I have checked the following claim for $n \le 7$ when $q=2$ and $n \le 5$ when $q=3$ by computer calculations. Note also that the $q$ -binomial factor $\binom{n-(r+s)}{r-s}_q$ counts, up to a power of $q$ , the number of $(r-s)$ -dimensional complements in $\mathbb{F}_q^n$ to a fixed subspace of dimension $r+s$ , in good analogy with the symmetric group case. But it seems some careful analysis of reduced row-echelon forms (like the argument for the degree of $G$ above, but too hard for me to to do in an evening) will be needed to nail down the power of $q$ . Examples 11.7 in James' lecture notes seem helpful.

Claim The adjacency matrix for the graph acts on $S^{(n-s,s)}$ by scalar multiplication by $(-1)^s q^{r^2 - rs + \binom{s}{2}}\binom{n-(r+s)}{r-s}_q$ .

Assuming the claim, the least eigenvalue is the one for $s=1$ , and it is $-q^{r^2-r} \binom{n-r-s}{r-s}_q$ . Putting this into Hoffman’s bound and using that the subspaces graph is regular of degree $\binom{n-r}{r}_q q^{r^2}$ as seen above we get that the maximum size of an independent set is at most

$\begin{aligned} \frac{\binom{n}{r}_q q^{r^2-r} \binom{n-r-1}{r-1}_q}{q^{r^2}\binom{n-r}{r}_q + q^{r^2-r}\binom{n-r-1}{r-1}_q} &= \frac{ \binom{n}{r}_q}{ q^r\binom{n-r}{r}_q/\binom{n-r-1}{r-1}_q + 1} \\ &= \frac{ \binom{n}{r}_q}{ q^r\frac{q^{n-r}-1}{q^r-1} + 1} \\ &= \textstyle \binom{n}{r} \frac{q^r-1}{q^r(q^{n-r}+1)+q^r-1} \\&= \textstyle \binom{n-1}{r-1}_q \end{aligned}$

which, somewhat spectacularly I feel, again comes out on the nose.

A Putnam problem

The second generalization ties 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.

This entry was posted on Thursday, June 8th, 2023 at 9:18 pm and is filed under Combinatorics, Representation theory, Symmetric group. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

	Matt Towers on The fixed point combinator and…
	mwildon on The fixed point combinator and…
	mwildon on Lines meeting planes: are ther…
	mwildon on Two proofs of Shannon’s…
	Syomantak on Two proofs of Shannon’s…

Wildon's Weblog