Graph Theory and $\mathfrak{sl}_2$

How many unlabeled graphs are there with $n$ vertices and $k$ edges?  Below is a graph of the number of isomorphism classes of (unlabeled graphs) on $7$ vertices.

Graphs on 7 vertices

• Number of Graphs

• Number of Graphs

The labels on the $x$-axis are the number of edges $k$; the $y$-axis indicates the number of graphs with $k$ edges

Observe that the number of graphs on $7$ vertices with $k$ edges is unimodal --- it has only one peak.  Indeed, if $g_{n,k}$ is the number of graphs with $n$ vertices and $k$ edges, the sequence

$$(g_{n, k})_{0\leq k\leq {n\choose 2}}$$  is always unimodal for fixed $n$.  The remarkable thing is that one can prove this fact using the representation theory of the Lie algebra $\mathfrak{sl}_2$.

Yesterday I gave a talk for the Columbia Undergraduate Math Society explaining this proof.  The use of $\mathfrak{sl}_2$ to prove unimodality is a well-known technique, which has been developed by Richard Stanley and others, but I find it quite difficult to understand the meat of these sorts of arguments when reading the combinatorics papers in which they appear, since they are often treated in the full generality of "posets with the Sperner property."  So I figured I'd sketch the argument in this case.  You can find full notes on my talk (which include a classification of the finite-dimensional irreducible representations of $\mathfrak{sl}_2$) here, or on my talks page.

Recall that an $n$-dimensional representation of $\mathfrak{sl}_2$ is the same as a triple of $n\times n$ matrices $E, F, G$ such that

$$[E,F]=H, [H,E]=2E, [H,F]=-2F.$$  The key fact we will need from the classification of $\mathfrak{sl}_2$-reps is the following:

Theorem 1.  Let $V$ be a finite-dimensional complex representation of $\mathfrak{sl}_2(\mathbb{C})$, and let $d_k(V)$ be the generalized eigenspace of $H$ corresponding to the eigenvalue $k$.  Then the sequences

$$(d_k(V))_{k\text{ odd}}, (d_k(V))_{k\text{ even}}$$ are unimodal.

This theorem follows trivially from the classification of finite-dimensional $\mathfrak{sl}_2$-representations.  (In fact, $H$ always acts diagonalizably, and its eigenvalues are always integers, but we won't use this.)  We call the (generalized) eigenspace of $H$ with eigenvalue $k$ the $k$-weight space.  We are now ready to prove:

Theorem 2. Fix a non-negative integer $n$.  Then the sequence

$$(g_{n, k})_{0\leq k\leq {n \choose 2}}$$ is unimodal.

Proof.  By the theorem, it suffices to construct an $\mathfrak{sl}_2$-rep $W_n$ such that the weight spaces of $W$ have dimension equal to $g_{n,k}$, and so that the eigenvalues of $H$ all have the same parity.  We let $G_{n,k}$ be the set of labelled graphs with $n$ vertices $\{1,\cdots, n\}$ and $k$ edges, and set $U_{n,k}=\mathbb{C}^{G_{n,k}}$.  That is, $U_{n,k}$ is a vector space with a basis consisting of labelled graphs on $n$ vertices and with $k$ edges.  The symmetric group $S_n$ acts on $U_{n,k}$ by permuting the vertices.  We set

$$U_n=\bigoplus_k U_{n,k}, W_{n,k}=U_{n,k}^{S_n}, W_n=\bigoplus_k W_{n,k}.$$

Proposition.  

$$\dim(W_{n,k})=g_{n,k}$$

Proof of Proposition.  Exercise.

In particular, it suffices to construct a $\mathfrak{sl}_2$-representation on $W_n$ whose weight spaces are the $W_{n,k}$, and all of whose eigenvalues have the same parity.  In fact, we will construct an $\mathfrak{sl}_2$-representation on $U_n$ which commutes with the $S_n$-action (and thus preserves $W_n$).

Let $e_{i,j}: U_n\to U_n$ be the operator (defined on the basis of labelled graphs)

$$e_{i,j}: g\mapsto \begin{cases}  g\cup (i,j) & \text{ if }(i,j)\not\in g\\ 0 & \text{otherwise}\end{cases}$$ and $f_{i,j}: U_n\to U_n$ the operator $$f_{i,j}: g \mapsto \begin{cases}  g\setminus (i,j) & \text{ if }(i,j)\in g\\ 0 & \text{otherwise.}\end{cases}$$  That is, $e_{i,j}$ adds an edge between vertices $i$ and $j$ if there isn't one there already, and sends a graph to $0$ otherwise; similarly $f_{i,j}$ removes the edge between $i$ and $j$ if there is one, and sends the graph to $0$ otherwise.  We set $$E=\sum_{i<j} e_{i,j}, F=\sum_{i<j} f_{i,j}, H=[E,F].$$  One may easily check that if $g$ is a graph with $k$ edges, then $$Hg=\left(2k-{n\choose 2}\right)g,$$ so the eigenspaces of $H$ are precisely the $U_{n,k}$.  Moreover $$[H, E]=2E, [H,F]=-2F.$$   Thus we have constructed the desired $\mathfrak{sl}_2$-representation on $U_n$; $F, E$ and hence $H$ commute with the $S_n$-action by definition, so we obtain the desired representation on $W_n=U_n^{S_n}$.  Now Theorem 2 follows immediately from Theorem 1. $\square$

Notes

One observation is that we've actually proven a lot more than we set out to -- indeed, if $\chi$ is any representation of the symmetric group, we've shown that the dimensions of the $\chi$-isotypic pieces of $U_{n,k}$ have unimodal-dimensions.  These pieces may be interpreted as spaces of functions on labelled graphs which transform in a certain way under relabelling.

The use of $\mathfrak{sl}_2$ to prove unimodality of combinatorial sequences is a pretty venerable technique -- for example, if $P_{k,\ell}(n)$ is the number of ways of partitioning $\ell$ into $k$ pieces of length at most $\ell$, one may prove that the sequence $P_{k, \ell}(n)$ for fixed $k,\ell$ and varying $n$ is unimodal using $\mathfrak{sl}_2$-representation theory.  This proof has a reinterpretation -- one may think of the representation in question as coming from the Hard Lefschetz Theorem on the cohomology of the Grassmannian!

Question.  Is there a smooth polarized variety with an $S_n$-action whose cohomology is isomorphic to $U_n$ above as an $S_n\times \mathfrak{sl}_2$-representation?  (Here the $\mathfrak{sl}_2$-representation comes from the polarization from Hard Lefschetz).

Richard Stanley has used the Hard Lefschetz theorem to prove amazing results about $f$-vectors of polytopes; more recently, June Huh, Eric Katz, and others have proven some really cool related combinatorial statements using algebraic geometry.