On the length of subgroup chains in the symmetric group
- 1 January 1986
- journal article
- research article
- Published by Taylor & Francis in Communications in Algebra
- Vol. 14 (9) , 1729-1736
- https://doi.org/10.1080/00927878608823393
Abstract
We prove that for n≥2, the length of every subgroup chain in Sn is at most 2n-3. The proof rests on an upper bound for the order of primitive permutation groups, due to Praeger and Saxl. The result has applications to worst case complexity estimates for permutation group algorithms.Keywords
This publication has 11 references indexed in Scilit:
- Polynomial-time algorithms for finding elements of prime order and sylow subgroupsJournal of Algorithms, 1985
- Sylow's theorem in polynomial timeJournal of Computer and System Sciences, 1985
- The transitive groups of degree up to eleven+Communications in Algebra, 1983
- A compact representation for permutation groupsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1982
- On the order of doubly transitive permutation groupsInventiones Mathematicae, 1982
- Isomorphism of graphs of bounded valence can be tested in polynomial timeJournal of Computer and System Sciences, 1982
- On the Order of Uniprimitive Permutation GroupsAnnals of Mathematics, 1981
- Finite Permutation Groups and Finite Simple GroupsBulletin of the London Mathematical Society, 1981
- On the orders of Primitive Permutation GroupsBulletin of the London Mathematical Society, 1980
- Some group-theoretic algorithmsLecture Notes in Mathematics, 1978