<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 3" %>
Multiplicity-Free Permutation Representations of the Symmetric Group
Chris Godsil1 and Karen Meagher2
1Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada
1Department of Mathematics and Statistics, University of Regina, Regina, Saskatchewan, Canada
Annals of Combinatorics 13 (4) pp.463-490 December, 2009
AMS Subject Classification: 20C30
We determine all the multiplicity-free representations of the symmetric group. This project is motivated by a combinatorial problem involving systems of set-partitions with a specific pattern of intersection.
Keywords: association schemes, multiplicity-free representations, finite symmetric group


1. Bannai, E.: Maximal subgroups of low rank of finite symmetric and alternating groups. J. Fac. Sci. Univ. Tokyo Sect. IA Math. 18, 475--–486 (1971/72)

2. Beaumont, R.A., Peterson, R.P.: Set-transitive permutation groups. Canad. J. Math. 7, 35--–42 (1955)

3. Colbourn, C.J., Dinitz, J.H., Stinson, D.R.: Applications of combinatorial designs to communications, cryptography, and networking. In: Surveys in combinatorics, pp. 37--–100. Cambridge Univ. Press, Cambridge (1999)

4. Curtis, C.W., Reiner, I.: Representation Theory of Finite Groups and Associative Algebras. John Wiley & Sons, New York-London (1962)

5. Fulton, W., Harris, J.: Representation Theory. Springer-Verlag, New York (1991)

6. The GAP Group, GAP — Groups, Algorithms, and Programming, Version 4.4.9. (2006) http://www.gap-system.org

7. Gargano, L., K¨orner, J., Vaccaro, U.: Qualitative independence and Sperner problems for directed graphs. J. Combin. Theory Ser. A 61, 173--–192 (1992)

8. Godsil, C.D., Newman, M.W.: Independent sets in association schemes. Combinatorica 26(4), 431--–443 (2006)

9. Liebeck, M.W., Praeger, C.E., Saxl, J.: Distance transitive graphs with symmetric or alternating automorphism group. Bull. Austral. Math. Soc. 35(1), 1--–25 (1987)

11. Mathon, R., Rosa, A.: A new strongly regular graph. J. Combin. Theory Ser. A 38(1), 84--–86 (1985)

12. Meagher, K.: Covering Arrays on Graphs: Qualitative Independence and Extremal Set Partition Theory. PhD thesis, University of Ottawa, Ottawa (2005)

13. Poljak, S., Pultr, A., R¨odl, V.: On qualitatively independent partitions and related problems. Discrete Appl. Math. 6(2), 193--–205 (1983)

14. Poljak, S., Tuza, Z.: On the maximum number of qualitatively independent partitions. J. Combin. Theory Ser. A 51(1), 111--–116 (1989)

15. Sagan, B.E.: The Symmetric Group. The Wadsworth & Brooks/Cole Mathematics Series, Pacific Grove, CA (1991)

16. Saxl, J.: Characters of multiply transitive permutation groups. J. Algebra 34, 528–--539 (1975)

17. Saxl, J.: On multiplicity-free permutation representations. In: Finite Geometries and Designs, pp. 337--–353. Cambridge Univ. Press, Cambridge-New York (1981)

18. Sims, C.C.: Computational methods in the study of permutation groups. In: Computational Problems in Abstract Algebra, pp. 169--–183. Pergamon, Oxford (1970)

19. Wielandt, H.: Finite permutation groups. Academic Press, New York-London (1964)

20. Wildon, M.: Multiplicity-free representations of symmetric groups. J. Pure Appl. Algebra 213, 146-- –1477 (2009)