1. Disjoint direct product decompositions of permutation groups
- Author
-
Mun See Chang, Christopher Jefferson, The Royal Society, University of St Andrews. School of Computer Science, University of St Andrews. Centre for Interdisciplinary Research in Computational Algebra, University of St Andrews. Centre for Research into Equality, Diversity & Inclusion, and University of St Andrews. St Andrews GAP Centre
- Subjects
QA75 ,QA75 Electronic computers. Computer science ,T-NDAS ,Group Theory (math.GR) ,Direct product ,010103 numerical & computational mathematics ,Disjoint sets ,01 natural sciences ,Combinatorics ,Subdirect product ,FOS: Mathematics ,Partition (number theory) ,0101 mathematics ,Time complexity ,Mathematics ,Decomposition ,Algebra and Number Theory ,010102 general mathematics ,Permutation group ,Computational Mathematics ,Computation ,Computer algebra system ,Mathematics - Group Theory - Abstract
Funding: The first author is supported by an Engineering and Physical Sciences Research Council grant (EP/P015638/1). The second author is supported by a Royal Society University Research Fellowship (URF\R\180015). Let H ≤ Sn be an intransitive group with orbits Ω1, Ω2, ... , Ωk. Then certainly H is a subdirect product of the direct product of its projections on each orbit, H|Ω1 x H|Ω2 x ... x H|Ωk. Here we provide a polynomial time algorithm for computing the finest partition P of the H-orbits such that H = Πc∈P H|c and we demonstrate its usefulness in some applications. Postprint
- Published
- 2022
- Full Text
- View/download PDF