Combinatorial Representation Theory

Arun Ram
Department of Mathematics and Statistics
University of Melbourne
Parkville, VIC 3010 Australia
aram@unimelb.edu.au

Last update: 17 September 2013

Part I

1. What is Combinatorial Representation Theory?

What do we mean by “combinatorial representation theory”? First and foremost, combinatorial representation theory is representation theory. The adjective “combinatorial” will refer to the way in which we answer representation theoretic questions. We will discuss this more fully later. For the moment let us begin with, what is representation theory?

What is representation theory?

If representation theory is a black box, or a machine, then the input is an algebra $A\text{.}$ The output of the machine is information about the modules for $A\text{.}$

An algebra is a vector space $A$ over $ℂ$ with a multiplication.

An important example is the case of the group algebra.

Define the group algebra of a group $G$ to be $$A=ℂG=ℂ\text{-span}\hspace{0.17em}\{g\in G\},$$ so that the elements of $G$ form a basis of $A\text{.}$ The multiplication in the group algebra is inherited from the multiplication in the group.

We want to study the algebra $A$ via its actions on vector spaces.

An $A\text{-module}$ is a finite dimensional vector space $M$ over $ℂ$ with an $A$ action.

See Appendix A1 for a complete definition. We shall use the words module and representation interchangeably. Representation theorists are always trying to break up modules into pieces.

An $A\text{-module}$ $M$ is indecomposable if $M\ncong M_1\oplus M_2$ where $M_1$ and $M_2$ are nonzero $A\text{-modules.}$

An $A\text{-module}$ $M$ is irreducible or simple if it has no submodules.

In reference to modules the words “irreducible” and “simple” are used completely interchangeably.

The algebra $A$ is semisimple if $$\text{indecomposable}\hspace{0.17em}=\hspace{0.17em}\text{irreducible}$$ for $A\text{-modules.}$

The “non-semisimple” case, i.e. where indecomposable is not the same as irreducible, is called modular representation theory. We will not consider this case much in these notes. However, before we banish it completely let us describe the flavor of modular representation theory.

A composition series for $M$ $$M=M_0\supseteq M_1\supseteq \cdots \supseteq M_k=0$$ is a sequence of submodules of $M$ such that each $M_i/M_{i+1}$ is simple.

The Jordan-Hölder theorem says that two different composition series of $M$ will always produce the same multiset $\{M_i/M_{i+1}\}$ of simple modules. Modular representation theorists are always trying to determine this multiset of composition factors of $M\text{.}$

Remarks.

(1)	We shall not make life difficult in this article but one should note that it is common to work over general fields rather than just using the field $ℂ\text{.}$
(2)	If one is bold one can relax things in the definition of module and let $M$ be infinite dimensional.
(3)	Of course the definition of irreducible modules is not correct since $0$ and $M$ are always submodules of $M\text{.}$ So we are ignoring these two submodules in this definition. But conceptually the definition is the right one, we want a simple module to be something that has no submodules.
(4)	The definition of semisimple above is not a technically correct definition. Look in Appendix A1 for the proper definition. However, the power of semisimplicity is exactly that it makes all indecomposable modules irreducible. So “indecomposable = irreducible” is really the right way to think of semisimplicity.
(5)	A good reference for the basics of representation theory is [CRe1988]. The book [Bou1958] contains a completely general and comprehensive treatment of the theory of semisimple algebras. The appendix, §A1, to this article also contains a brief (and technically correct) introduction with more specific references.

Main questions in representation theory

I. What are the irreducible $A\text{-modules?}$

What do we mean by this question? We would like to be able to give some kind of answers to the following more specific questions.

(a)	How do we index/count them?
(b)	What are their dimensions?
	The dimension of a module is just its dimension as a vector space.
(c)	What are their characters?
	The character of a module $M$ is the function ${\chi }_M:A\to ℂ,$ where ${\chi }_M\left(a\right)$ is the trace of the linear transformation determined by the action of $a$ on $M\text{.}$ More precisely, $${\chi }_M\left(a\right)=\sum _{b_i\in B}a{b}_i{|}_{b_i},$$ where the sum is over a basis $B$ of the module $M$ and $a{b}_i{|}_{b_i}$ denotes the coefficient of $b_i$ in $a{b}_i$ when we expand in terms of the basis $B\text{.}$

C. How do we construct the irreducible modules?

S. Special/Interesting representations $M$

(a)	How does $M$ decompose into irreducibles?
	If we are in the semisimple case then $M$ will always be a direct sum of irreducible modules. If we group the irreducibles of the same type together we can write $$M\cong \underset{\lambda }{⨁}{\left(V^{\lambda }\right)}^{\oplus c_{\lambda }},$$ where the modules $V^{\lambda }$ are the irreducible $A\text{-modules}$ and $c_{\lambda }$ is the number of times an irreducible of type $V^{\lambda }$ appears as a summand in $M\text{.}$ It is common to abuse notation and write $$M=\sum _{\lambda }{c}_{\lambda }{V}^{\lambda }\text{.}$$
(b)	What is the character of $M\text{?}$
	Special modules often have particularly nice formulas describing their characters. It is important to note that having a nice character formula for $M$ does not necessarily mean that it is easy to see how $M$ decomposes into irreducibles. Thus this question really is different from the previous one.
(c)	How do we find interesting representations?
	Sometimes special representations turn up by themselves and other times one has to work hard to construct the right representation with the right properties. Often very interesting representations come from other fields.
(d)	Are they useful?
	A representation may be particularly interesting just because of its structure while other times it is a special representation that helps to prove some particularly elusive theorem. Sometimes these representations lead to a completely new understanding of previously known facts. A famous example (which unfortunately we won’t have space to discuss, see [Hum1978]) is the Verma module, which was discovered in the mid 1960s and completely changed representation theory.

M. The modular case

In the modular case we have the following important question in addition to those above.

(a)	What are the indecomposable representations?
(b)	What are the structures of their composition series?

For each indecomposable module $M$ there is a multiset of irreducibles $\{M_i/M_{i+1}\}$ determined by a composition series of $M\text{.}$ One would like to determine this multiset.

Even better (especially for combinatorialists), the submodules of $M$ form a lattice under inclusion of submodules and one would like to understand this lattice. This lattice is always a modular lattice and we may imagine that each edge of the Hasse diagram is labeled by the simple module $N_1/N_2$ where $N_1$ and $N_2$ are the modules on the ends of the edge. With this point of view the various compositions series of $M$ are the maximal chains in this lattice of modules. The Jordan-Hölder theorem says that every maximal chain in the lattice of submodules of $M$ has the same multiset of labels on its edges. What modular representation theorists try to do is determine the set of labels on a maximal chain.

Remark. The abuse of notation which allows us to write $M={\sum }_{\lambda }{c}_{\lambda }{V}^{\lambda }$ has been given a formal setting which is called the Grothendieck ring. In other words, the formal object which allows us to write such identities has been defined carefully. See [Ser1977] for precise definitions of the Grothendieck ring.

Answers should be of the form...

Now we come to the adjective “Combinatorial.” It refers to the way in which we give the answers to the main questions of representation theory.

I. What are the irreducible $A\text{-modules?}$

(a)	How do we index/count them?
	We want to answer with a bijection between $$\text{Nice combinatorial objects}\hspace{0.17em}\lambda \stackrel{1-1}{⟷}\text{Irreducible representations}\hspace{0.17em}{V}^{\lambda }\text{.}$$
(b)	What are their dimensions?
	We should answer with a formula of the form $$\text{dim}\left(V^{\lambda }\right)=\text{\# of nice combinatorial objects.}$$
(c)	What are their characters?
	We want a character formula of the type $$\chi \left(a\right)=\sum _T{\text{wt}}^a\left(T\right),$$ where the sum runs over all $T$ in a set of nice combinatorial objects and ${\text{wt}}^a$ is a weight on these objects which depends on the element $a\in A$ where we are evaluating the character.

C. How do we construct the irreducible modules?

We want to give constructions that have a very explicit and very combinatorial flavor. What we mean by this will be more clear from the examples, see (C1-2) of Section 2.

S. Special/Interesting representations $M$

(a)	How does $M$ decompose into irreducibles?
	If $M$ is an interesting representation we want to determine the positive integers $c_{\lambda }$ in the decomposition $$M\cong \underset{\lambda }{⨁}{\left(V^{\lambda }\right)}^{\oplus c_{\lambda }}$$ in the form $$c_{\lambda }=\text{\# of nice combinatorial objects.}$$ In the formula for the decomposition of $M$ the sum is over all $\lambda$ which are objects indexing the irreducible representations of $A\text{.}$
(b)	What is the character of $M\text{?}$
	As in the case I(c) we want a character formula of the type $${\chi }_M\left(a\right)=\sum _T{\text{wt}}^a\left(T\right)$$ where the sum runs over all $T$ in some set of nice combinatorial objects and ${\text{wt}}^a$ is a weight on these objects which depends on the element $a\in A$ where we are evaluating the character.
(c)	How do we find interesting representations?
	It is particularly pleasing when interesting representations arise in other parts of combinatorics! One such example is a representation on the homology of the partition lattice which also, miraculously, appears as a representation on the free Lie algebra. We won’t have space to discuss this here, see the original references [Han1981],[Joy1986], [Kly1974], [Sta1982], the article [Gar1990] for some further basics, and [Bar1990] for a study of how it can be that this representation appears in two completely different places.
(d)	Are they useful?
	How about for solving combinatorial problems? Or making new combinatorial problems? Sometimes a representation is exactly what is most helpful for solving a combinatorial problem. One example of this is in the recent solution of the the last few plane partition conjectures. See [Sta1971], [Mac1995] I §5 Ex. 13-18, for the statement of the problem and [Kup1994,Kup1994-2,Kup1996] and [Ste1995,Ste1994-2] for the solutions. These solutions were motivated by the method of Proctor [Pro1984].

The main point of all this is that a combinatorialist thinks in a special way (nice objects, bijections, weighted objects, etc.) and this method of thinking should be an integral part of the form of the solution to the problem.

Notes and references

This is the survey paper Combinatorial Representation Theory, written by Hélène Barcelo and Arun Ram.

Key words and phrases. Algebraic combinatorics, representations.

Barcelo was supported in part by National Science Foundation grant DMS-9510655.
Ram was supported in part by National Science Foundation grant DMS-9622985.
This paper was written while both authors were in residence at MSRI. We are grateful for the hospitality and financial support of MSRI..

page history