Applications of Representation Theory in Combinatorics

Question

What are the examples of interesting combinatorial identities (e.g. bijection between two sets of combinatorial objects) that can be proved using representation theory, or has some representation theoretic interpretation. Please also mention whether a purely combinatorial proof is known in each case.

Answer 1

It is unclear exactly what is meant by a "combinatorial identity." For instance, let $X_n$ denote the set of alternating permutations in the symmetric group $\mathfrak{S}_n$ that are also cycles of length $n$. Then $$ \#X_n = \frac 1n\sum_{d|n}\mu(d)(-1)^{(d-1)/2}E_{n/d}, $$ where $E_{n/d}$ is an Euler number. Assuming that this counts as a combinatorial identity, then there are many further results of this nature at http://math.mit.edu/~rstan/papers/altenum.pdf. The only known proofs of most of them (including the one above, even when $n$ is prime) use the representation theory of the symmetric group.

Another identity which has no combinatorial proof is $$ \frac{1}{n!}\sum_{u,v\in\mathfrak{S}_n} q^{\kappa(uvu^{-1}v^{-1})} = \sum_{\lambda\vdash n}\prod_{t\in\lambda} (q+c(t)), $$ where $\kappa(w)$ is the number of cycles of $w$, and $c(t)$ is the content of the square $t$ of (the diagram of) $\lambda$. This is Exercise 7.68(e) of my book Enumerative Combinatorics, vol. 2. Many other similar results appear near this exercise.

Answer 2

Let $$(\ast) \qquad g(\alpha,\beta,\gamma) := \sum_{\sigma,\omega,\pi} \text{sign}(\sigma\omega\pi) \, C(\alpha-\sigma,\beta-\omega,\gamma-\pi), $$ where $\alpha,\beta,\gamma \vdash n$ are partitions with $\le \ell$ rows viewed as vectors in $\Bbb R^\ell$, $C(x,y,z)$ is the number of $\ell\times \ell \times \ell$ contingency arrays with 2-dim sums given by vectors $x,y,z$, and the sum is over triples $\sigma,\omega,\pi$ of permutations of $\{0,1,\ldots,\ell-1\}$.

Now $g(\alpha,\beta,\gamma)$ is the Kronecker coefficient, and we have the inequality $$ g(\alpha,\beta,\gamma) \ge 0. $$ Finding a combinatorial proof of this inequality is a major problem in this case.

P.S. For $(\ast)$, see e.g. eq. (8) in our paper On the complexity of computing Kronecker coefficients.

Answer 3

Alon and Kozma re-proved Kirchoff’s matrix-tree theorem using representation theory of $S_n$:

Let $G$ be any weighted graph, and denote by $w_e$ the weight of the edge $e$. For a spanning tree $T$, denote $w(T) = \prod_{e \in T} w_e$, where the product is over all edges $e$ of $T$. Finally denote by $0 = \lambda_0 \le \lambda_1 \le \cdots \le \lambda_{n-1}$ the eigenvalues of the continuous time Laplacian $\Delta_G$. Then $$\sum_{T} w(T) = \frac{1}{n} \prod_{i=1}^{n-1} \lambda_i.$$

It was actually a corollary of a result on some mixing properties of the interchange process (a natural occurring random walk on $S_n$).

See the Appendix of their paper.

Of course, the old theorem has many classical proofs, but representation theory gives a new angle.

Answer 4

The FFT on permutations is intimately connected with the representation of the Symmetric group:

See "Group theoretical methods in Machine Learning" by Risi Kondor.

Answer 5

Many plane partition enumeration formulae have proofs using representation theory. For example, let $PP((p)^q,m)$ denote the $p \times q$ plane partitions of height at most $m$. For $p > q$, let $PP(\nabla_{p,q},m)$ denote the plane partitions of shifted shape $\nabla_{p,q} = (p+q-1, p+q-3, \dots, p-q+1)$ of height at most $m$. Tje $(p)^q$ plane partition describe weights of irreducible representations in $sl(p+q,\mathbb{C})$ while the $\nabla_{p,q}$ plane partitions describe weights of irreducible $sp(2k,\mathbb{C})$ representations when $p +q = 2k$. In this paper, Proctor showed that $$ |PP(\nabla_{p,q},k)| = |PP((p)^q,k)| = \prod^p_{i=1} \prod^q_{j=1}\prod^m_{k=1} \frac{(i+j+k-1)}{(i+j+k-2)}, $$ where the second equality is a well known result of MacMahon's. His proof used a branching rule to show the irreducible representations in question are equinumerous, and at present no bijective proof has been published.

Answer 6

Maschke tells you that $\mathbb C[G] \cong \bigoplus_V V^*\otimes V$, where $V$ runs over the irreps of a finite group $G$. Apply this to $G= S_n$ and take dimensions, and you get $n! = \sum_{\lambda \vdash n} \#SYT(\lambda)^2$, which can be proven combinatorially with the Robinson-Schensted correspondence.

Generalizing this, consider the $GL(k)\times GL(n)$-representation $Sym(Hom(\mathbb C^k,\mathbb C^n)) \cong \bigoplus_{\lambda_1 \geq \ldots \geq \lambda_{\min(k,n)}} (V^{GL(k)}_\lambda)^* \otimes V^{GL(n)}_\lambda$. The LHS has a basis of monomials, corresponding to $k\times n$ matrices of naturals. The RHS has a basis of pairs of same-shape SSYT. This $\cong$ can be proven combinatorially, the RSK correspondence. There is another such story with $Alt$ in place of $Sym$.

Answer 7

Define a partition move to be the removal and then addition of a box of the Young diagram of a partition. Thus there are unique partition moves from $(2,1)$ to $(3)$ and from $(2,1)$ to $(1,1,1)$, and two moves (corresponding to the two removable boxes) from $(2,1)$ to $(2,1)$. Let $M_t(n)$ be the number of sequences of $t$ partition moves from $(n)$ to $(n)$. For example, $M_3(2) = 4$.

In a joint paper with John Britnell we used the descent algebra of the symmetric group to show that $M_t(n)$ is the number of set partitions of $\{1,\ldots,t\}$ into at most $n$ subsets.

We do not have a bijective proof of this identity. There is a natural candidate for a bijection, using the RSK-correspondence; rather unexpectedly, this bijection works for all $t \le 7$ and $n\le 12$, but fails for $t = 8$ and $n=5$. (See Proposition 7.2 in the paper.)

Answer 8

Here's an example that involves a group other than the symmetric group.

Let ${\mathbb F}_{q^n}$ denote the finite field with $q^n$ elements. Since ${\mathbb F}_{q^n}$ is a vector space of dimension $n$ over ${\mathbb F}_q$, we may regard a generator of the multiplicative group ${\mathbb F}^*_{q^n}$ as an element of $GL_n({\mathbb F}_q)$; define a Singer cycle to be such a generator. Also define a reflection to be a nontrivial element of $GL_n({\mathbb F}_q)$ whose fixed points form a hyperplane.

Theorem (Lewis–Reiner–Stanton). The number of factorizations of a Singer cycle into a product of $n$ reflections is $(q^n-1)^{n-1}$.

The only known proof uses the character theory of $GL_n({\mathbb F}_q)$ in an essential way.

Note that the above theorem is analogous to the classical result that the number of factorizations of an $n$-cycle in ${\mathfrak S}_n$ into a product of $n-1$ transpositions is $n^{n-2}$.

Answer 9

Given $k$ conjugacy classes $C_1,C_2,\dots,C_k$ in a finite group $G$ with unity $e$, we may ask what is the probability $p(C_1,\dots,C_k)$ that $g_1\dots g_k=e$ if $g_i\in C_i$ is chosen uniformly at random. In the (say, complex) group algebra $\mathbb{C}[G]$ it is just the coefficient of $e$ in the product $\prod_{i=1}^k \varphi_i$, where we denote $$\varphi_i=|C_i|^{-1}\sum\limits_{g\in С_i} g.$$ It is natural to expand central functions $\varphi_i$ as linear combinations of irreducible characters (we identify an irreducible character $\chi$ on the group $G$ and the element $\sum \chi(g) g$ of $\mathbb{C}[G]$, which we again denote $\chi$.) These elements $\chi$ satisfy simple algebraic relations in the group algebra: $\chi_1\chi_2=0$ for $\chi_1\ne \chi_2$, $\chi^2=\frac{|G|}{\dim \chi} \chi$. This is bit more delicate property of characters than what is usually called `orthogonality relations'. We have $$\varphi_i=|G|^{-1}\sum_{\chi} \bar{\chi}(c_i)\cdot \chi,$$ where summation is taken over all irreducible characters and $c_i\in C_i$ are arbitrary fixed elements. This is just the orthogonality relation itself. Well, now substitute this expression of $\varphi_i$ and expand brackets in $\prod_{i=1}^k \varphi_i$. Summands which contain at least two different characters disappear. Thus we have
$$ p(C_1,\dots,C_k)=[e] \prod_{i=1}^k \varphi_i=|G|^{-k}\sum_{\chi} [e]\frac{|G|^{k-1}\prod_{i=1}^k \bar{\chi}(c_i)}{(\dim \chi)^{k-1}}\chi=|G|^{-1}\sum_{\chi}\frac{\prod_{i=1}^k \bar{\chi}(c_i)}{(\dim \chi)^{k-2}}. $$ This formula is particularly useful for the symmetric group $G=S_n$, where we may use combinatorial formulae of Murnaghan - Nakayama for the values of characters. For example, if $C_1$ is the class of a long cycle, there exist only $n$ characters for which $\chi(c_1)\ne 0$. The following is Boccara's nice formula for the case $C_1=C_2=$(long cycles), $C_3$=class with cyclic type $(\lambda_1,\dots,\lambda_m)$: $$ p(C_1,C_2,C_3)=\frac1{(n-1)!}\int_0^1 \prod_{i=1}^m (x^{\lambda_i}-(x-1)^{\lambda_i})dx. $$ So, for $C_3=C_2=C_1$ (and odd $n$) we get that a probability that product of two long cycles is again a long cycle equals $2/(n+1)$.

See more on product of cycles in the slides by Richard Stanley.

This allows to get a number of combinatorial results on product of classes is the symmetric group $S_n$.

Answer 10

One of the most well known applications of representation theory in combinatorics is the explicit construction of Expander graphs by Margulis (using Kazhdan's property (T)). See any book about expanders (such as Lubotzky's) for example. The combinatorial statement in this case can be thought as having bounded Cheeger constant, or equivalently bounding the Rayleigh quotient.

EDIT - in order to address the last sentence, a non-constructive proof (by the probabilistic method) was known before Margulis' construction (probably due to Kolmogorov, but usually formally attributed to Pinsker). Since Margulis, a whole industry of explicit constructions has been developed, most notably with applications of arithmetic combinatorics in the last few years (what's known as the Bourgain-Gamburd method), although one might argue whether arithmetic combinatorics is part of combinatorics or harmonic analysis.

Answer 11

It seems to me that all answers to this question will involve the symmetric group. Here is one example from the representation theory of $S_n$ over a field of characteristic $2$: $$ \prod_{i=1}^\infty(1-x^i)^{-1}=\prod_{i=1}^\infty(1-x^{2i})^{-2}\sum_{n=0}^\infty x^{n(n+1)/2}. $$ The left hand side is the generating function for partitions - the coefficient of $x^n$ is the number of partitions of $n$. The right hand side reflects the way the partitions of $n$ split into $2$-blocks of partitions, according to their $2$-cores. The $2$-cores have the form $[n,n-1,\dots,2,1]$ giving the sum on the extreme right. The other infinite product refers to pairs of partitions, and arises from the enumeration of partitions in a block using a $2$-abacus. Now this equality rearranges and simplifies to $$ \prod_{i=1}^\infty\frac{(1-x^{2i})}{(1-x^{2i-1})}=\sum_{n=1}^\infty x^{n(n+1)/2}. $$ The left hand side ranges over all partitions with all even parts distinct; a partition with $e$ distinct even parts contributes $(-1)^e$ to the sum.

So for $n$ not a triangular number, the number of partitions with an odd number of distinct even parts must equal the number of partitions with an even number of distinct even parts. This is not obvious to me, but it recalls Euler's famous pentagonal number theorem.

More generally, let $t>0$ and let $c_n$ be the number of $t$-cores of $n$. Then $C_t(x)=\sum_{n=0}^\infty c_nx^n$ is the generating function for $t$-cores. Apart from $t=2$, there does not seem to be any simple description of $C_t(x)$, although it is known that $c_n>0$ for all $n$ and $t>3$ a prime. Then the $t$-abacus idea gives $$ \prod_{i=1}^\infty(1-x^i)^{-1}=\prod_{i=1}^\infty(1-x^{ti})^{-t}C_t(x). $$

Answer 12

Many identities involving multiplicative structure constants originate in representation theory. There are plenty of positivity statements about such structure constants but no combinatorial proof is known, or appeared much later. See the related question here about unsolved problems in representation theory.

One example is the Schubert structure constants (the constants appearing when a product of Schubert polynomials is again expanded in Schubert polynomials). For representation-theoretical reasons, these are non-negative integers, but it is completely mysterious why.

There is also certain symmetries in the Macdonald polynomials and diagonal harmonics, which are evident from the definition, but completely unclear from the current combinatorial models.

Answer 13

You may be interested in Yuval Filmus's survey paper Spectral Methods for Intersection Problems (Friedgut's Research Program in Extremal Combinatorics) (and/or his thesis which seems to have exactly the same title), which purports to explain how a number of combinatorial results along the lines of the Erdős-Ko-Rado theorem can be proved using representation theory. (I'm not sure one should call such results "identities", however: they're more along the lines of maximal combinatorics.)

Answer 14

The Robinson-Schensted correspondence has already been mentioned in another answer, as providing a bijection between permutations of $\{1,\dots,n\}$ and pairs of standard Young tableaux of the same shape (corresponding to partitions of $n$).

But this correspondence goes even further, since it provides three equivalence relations on the permutations (same left tableau, same right tableau, same shape), and in fact these equivalence relations are the same as those defining the left-, right- and twosided Kazhdan-Lusztig cells, when $S_n$ is seen as the Weyl group in type $A_{n-1}$.
Further, the twosided order on the twosided cells coincides with the dominance order of the tableau (i.e. partitions) determined by the twosided cells.
So this is an example of a combinatorial thing having a representation theoretic interpretation.