Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-24T16:14:43.598Z Has data issue: false hasContentIssue false
  • English
  • Français

Algorithmic Recognition of Actions of 2-Homogeneous Groups on Pairs

Published online by Cambridge University Press:  01 February 2010

Graham R. Sharp

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We give an algorithm that takes as input a transitive permutation group (G, Ω) of degree n={m\choose 2}, and decides whether or not Ω is G-isomorphic to the action of G on the set of unordered pairs of some set Γ on which G acts 2-homogeneously. The algorithm is constructive: if a suitable action exists, then one such will be found, together with a suitable isomorphism. We give a deterministic O(sn logcn) implemention of the algorithm that assumes advance knowledge of the suborbits of (G, Ω). This leads to deterministic O(sn2) and Monte-Carlo O(sn logcn) implementations that do not make this assumption.

Type
Research Article
Information
LMS Journal of Computation and Mathematics , Volume 1 , 1998 , pp. 109 - 147
Copyright
Copyright © London Mathematical Society 1998

References

1. Babai, L., Cooperman, G., Finkelstein, L. and Seress, Á., ‘Nearly linear time algorithms for permutation groups with a small base‘, Proceedings 1991 ACM International Symposium on Symbolic and Algebraic Computation (ed. Watt, S. M., American Mathematical Society, Providence RI, 1991), pp. 200–209.Google Scholar
2. Burnside, William, The Theory of Groups of Finite Order (Cambridge University Press, 1911) 2nd edn.Google Scholar
3. Cameron, Peter J. and Cannon, John J., ‘Fast recognition of doubly transitive groups‘, Journal of Symbolic Computation 12 (1991) 459–474.CrossRefGoogle Scholar
4. Dixon, John D. and Mortimer, Brian, Permutation Groups, Graduate Texts in Mathematics 163 (Springer-Verlag, New York, 1996).Google Scholar
5. Feit, W. and Thompson, J.G., ‘Solvability of groups of odd order‘, Pacific J. Math. 13 (1963) 775–1029.Google Scholar
6. Neumann, Peter M., ‘Some algorithms for computing with finite permutation groups‘, Proceedings of Groups–St. Andrews 1985 (eds E.F. Robertson and C.M. Campbell), L.M.S. Lecture Note Series 121 (Cambridge University Press, 1987), pp. 59–92.Google Scholar
7. Schönert, Martin and Seress, Ákos, ‘Finding blocks of imprimitivity in small-base groups in nearly linear time‘, Proceedings 1994 ACM-SIGSAM International Symposium on Symbolic and Algebraic Computation (1994), pp. 154–157.Google Scholar
8. Schönert, Martin et al. , GAP–Groups, Algorithms and Programming. (Lehrstuhl D für Mathematik, Rheinisch Westfälische Technische Hochschule, Aachen, Germany, 1994).Google Scholar
9. Wielandt, H., Finite Permutation Groups (Academic Press, New York, 1964).Google Scholar
Supplementary material: File

JCM 1 Sharp Appendix C

Sharp Appendix C

Download JCM 1 Sharp Appendix C(File)
File 53 KB