Last update: 17 September 2013
Most people in the field of combinatorial representation theory agree that the field begins with the fundamental results for the symmetric group Let us give the answers to the main questions for the case of The precise definitions of all the objects used below can be found in Appendix A2. As always, by a representation of the symmetric group we mean a representation of its group algebra
|(a)||How do we index/count them?|
|There is a bijection|
|(b)||What are their dimensions?|
|The dimension of the irreducible representation is given by where is the hook length at the box in see Appendix A2.|
|(c)||What are their characters?|
|Let be the character of the irreducible representation evaluated at a permutation of cycle type Then the character is given by where the sum is over all standard tableaux of shape and where and In the formula for sw means strictly south and weakly west and ne means strictly north and weakly east.|
There are several interesting constructions of the irreducible
via Young symmetrizers.
Let be a tableau. Let where is the sign of the permutation Then where the action of the symmetric group is by left multiplication.
Young’s seminormal construction.
Let so that the vectors are a basis of The action of on is given by and In this formula There are other important constructions of the irreducible representations We do not have room to discuss these constructions here, see the Notes and References (10-12) below and A3 in the appendix. The main ones are:
|(iii)||Young’s orthonormal construction,|
|(iv)||The Kazhdan-Lusztig construction,|
|(v)||The Springer construction.|
|(S1)||Let The module is the same as except that we only look Then where is the number of column strict fillings of of content such that the word of the filling is a lattice permutation. The positive integers are the Littlewood-Richardson coefficients. See Appendix A2.|
|(S2)||Let be a partition of Let The module is the vector space where the action of on the cosets is by left multiplication. Then where This representation also occurs in the following context: where is a unipotent element of with Jordan decomposition and is the variety of Borel subgroups in containing This representation is related to the Springer construction mentioned in C(v) above. See Appendix A3 for further details.|
|(S3)||If then the tensor product is defined by for all and There are positive integers such that Except for a few special cases the positive integers are still unknown. See [Rem1992] for a combinatorial description of the cases for which the coefficients are known.|
Notes and references
|(1)||The bijection in (Ia), between irreducible representations and partitions, is due to Frobenius [Fro1900]. Frobenius is the founder of representation theory and the symmetric group was one of the first examples that he worked out.|
|(2)||The formula in (Ib) for the dimension of as the number of standard tableaux is immediate from the work of Frobenius, but it really came into the fore from the work of Young [You1901-1952]. The “hook formula” for is due to Frame-Robinson-Thrall [FRT1954].|
|(3)||The formula for the characters of the symmetric group which is given in (Ic) is due to Fomin and Greene [FGr1998]. For them, this formula arose by application of their theory of noncommutative symmetric functions. Roichman [Roi1997] discovered this formula independently in the more general case of the Iwahori-Hecke algebra. The formula for the Iwahori-Hecke algebra is exactly the same as the formula for the case except that the 1 appearing in case 3 of the definition of should be changed to a|
|(4)||There is a different and more classical formula for the characters than the formula given in (Ic) which is called the Murnaghan-Nakayama rule [Mur1937] [Nak1940]. We have described the Murnaghan-Nakayama rule in the appendix, Theorem A2.2. Once the formula in (Ic) is given it is not hard to show combinatorially that it is equivalent to the Murnaghan-Nakayama rule but if one does not know the formula it is nontrivial to guess it from the Murnaghan-Nakayama rule.|
|(5)||We do not know if anyone has compared the algorithmic complexity of the formula given in (Ic) with the algorithmic complexity of the Murnaghan-Nakayama rule. One would expect that they have the same complexity: the formula above is a sum over more objects than the sum in the Murnaghan-Nakayama rule but these objects are easier to create and many of them have zero weight.|
|(6)||One of the beautiful things about the formula for the character of which is given in (Ic) is that it is a sum over the same set that we have used to describe the dimension of|
|(7)||The construction of by Young symmetrizers is due to Young [You1900,You1902] from 1900. It is used so often and has so many applications that it is considered classical. A review and generalization of this construction to skew shapes appears in [GWa1989].|
|(8)||The seminormal form construction of is also due to Young [You1931,You1934] although it was discovered some thirty years after the Young symmetrizer construction.|
|(9)||Young’s orthonormal construction differs from the seminormal construction only by multiplication of the basis vectors by certain constants. A comprehensive treatment of all three constructions of Young is given in the book by Rutherford [Rut1948].|
|(10)||The Kazhdan-Lusztig construction uses the Iwahori-Hecke algebra in a crucial way. It is combinatorial but relies crucially on certain polynomials which seem to be impossible to compute in practice except for very small see [Bre1994] for further information. This construction has important connections to geometry and other parts of representation theory. The paper [GMa1988] and the book [Hum1990] give elementary treatments of the Kazhdan-Lusztig construction.|
|(11)||Springer’s construction is a geometric construction. In this construction the irreducible module is realized as the top cohomology group of a certain variety, see [Spr1978], [CGi1997], and Appendix A3.|
|(12)||There are many ways of constructing new representations from old ones. Among the common techniques are restriction, induction, and tensoring. The special representations (S1), (S2), and (S3) given above are particularly nice examples of these constructions. One should note that tensoring of representations works for group algebras (and Hopf algebras) but not for general algebras.|
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..