<%@ 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
cgodsil@math.uwaterloo.ca
1Department of Mathematics and Statistics, University of Regina, Regina, Saskatchewan, Canada
kmeagher@math.uregina.ca
Annals of Combinatorics 13 (4) pp.463-490 December, 2009
AMS Subject Classification: 20C30
Abstract:
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

References:

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)