Examples of combinatorial problems where the only known solutions, or most "natural" solutions, use representation theory?

Question

In Solution of two difficult combinatorial problems with linear algebra, Robert Proctor presents two simply stated combinatorial problems, and gives solutions to them using a linear algebraic approach that is motivated by the representation theory of $\mathfrak{sl}_2(\mathbb{C})$. Moreover, he notes that this application is in some sense natural and inherent here, because both problems being considered are equivalently formulated as asking whether certain posets meet the conditions of being "rank unimodal" and "Sperner," and any poset satisfying these two conditions together with some additional symmetry constraints carries a representation of $\mathfrak{sl}_2(\mathbb{C})$.

My question: beyond the problems discussed in the link above and the references therein, are there other examples of combinatorial problems whose only known solution, or whose most motivated and natural solution, employs representation theory?

Answer 1

For a partition $\lambda$, let $y_k(\lambda)$ denote the number of Standard Young Tableaux $T$ of shape $\lambda$ satisfying $\mathrm{maj}(T)\equiv 1 \mod k$. (Here $\mathrm{maj}(T)$ is the major index of $T$, the sum of the descents of $T$, where $i$ is a descent of $T$ if $i$ appears in a row above $i+1$ in $T$.)

Then, according to Stanley, Enumerative Combinatorics, Vol. 2, Chapter 7 Exercise 7.88(d), there is no known combinatorial proof of the fact that $y_{n-1}(\lambda) \geq y_n(\lambda)$ for any partition $\lambda\vdash n$, although there is a proof using the representation theory of the symmetric group $S_n$.

I found this by searching for the phrase "no combinatorial proof is known" in EC1 and EC2.

Answer 2

Here's an example I found by searching "combinatorial proof" in Stanley's supplemental problems to EC2 Chapter 7: see here for the problems and here for the solutions.

If you look at the solution to problem 106(b) there, you will see Stanley notes that it implies $$ \#\{(u,v)\in S_n\times S_n\colon uv = vu\} = \#\{(u,v)\in S_n \times S_n \colon u^2=v^2 \}.$$ Here $S_n$ is the symmetric group on $n$ letters. The proof is via some symmetric function identities and Stanley remarks that the same is true for any finite group $G$ all of whose complex representations are equivalent to real representations.

He asks there if there is a combinatorial proof of this identity. I have no idea if this is easy.

EDIT: This is Exercise 108(b) in the Supplementary Problems of Chapter 7 as in the published version of the 2nd edition of EC2.

Answer 3

Many special cases of the Černý conjecture in automata theory have been proved using linear algebra, or really representations of monoids, that do not have known combinatorial proofs. The conjecture states that an $n$-state synchronizing automaton has a synchronizing word of length at most $(n-1)^2$. In purely mathematical terms the conjecture states that given a set of transformations of an $n$-element set, of which some composition (with repetitions allowed) is a constant map, then some composition of length at most $(n-1)^2$ is a constant map.

Many proof analyze the corresponding linear representation of the monoid generated by these transformations. My favorite example is the paper of Dubuc, which proves the conjecture is true if one of the transformations is an $n$-cycle. Černý had already shown that the bound can be reached by examples with an $n$-cycle. Dubuc uses the nature of representations of the cyclic group over the rationals (or if you like uses minimal polynomials). But there are many more such examples.