Two-closures of supersolvable permutation groups in polynomial time

DOI10.1007/S00037-020-00195-7MaRDI QIDQ777912zbMATH OpenOpenAlexFDO

Authors Ilya Ponomarenko, Andrey Vasil'ev

Publication date 8 July 2020

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1912.10217

zbMATH Keywords

permutation grouppolynomial-time algorithm2-closure

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) General theory for finite permutation groups (20B05) Finite automorphism groups of algebraic, geometric, or combinatorial structures (20B25) Computational methods for problems pertaining to group theory (20-08)

Abstract: The $2$-closure $overlineG$ of a permutation group $G$ on $Omega$ is defined to be the largest permutation group on $Omega$, having the same orbits on $OmegaimesOmega$ as $G$. It is proved that if $G$ is supersolvable, then $overlineG$ can be found in polynomial time in $|Omega|$. As a byproduct of our technique, it is shown that the composition factors of $overlineG$ are cyclic or alternating of prime degree.

Recommendations

• Two-closure of odd permutation group in polynomial time
• On the 2-Closures of Finite Permutation Groups
• Two-closure of rank \(3\) groups in polynomial time
• 2-closures of primitive permutation groups of holomorph type
• The 2-closure of a \(\frac{3}{2}\)-transitive group in polynomial time

Cites work

• scientific article; zbMATH DE number 3906699 (Why is no real title available?)
• scientific article; zbMATH DE number 3710402 (Why is no real title available?)
• scientific article; zbMATH DE number 1849958 (Why is no real title available?)
• scientific article; zbMATH DE number 894528 (Why is no real title available?)
• scientific article; zbMATH DE number 3223737 (Why is no real title available?)
• 2-closures of primitive permutation groups of holomorph type
• Circulant graphs: recognizing and isomorphism testing in polynomial time
• Closures of Finite Primitive Permutation Groups
• Coherent configurations. I: Ordinary representation theory
• Counterexamples to two conjectures in the Kourovka notebook
• Cyclic regular subgroups of primitive permutation groups
• Finding the automorphism group of a circulant association scheme in polynomial time
• GROUP, GRAPHS, ALGORITHMS: THE GRAPH ISOMORPHISM PROBLEM
• Graph isomorphism problem and \(2\)-closed permutation groups
• Invariant relations and Aschbacher classes of finite linear groups.
• On the 2-Closures of Finite Permutation Groups
• Permutation group approach to association schemes
• Permutation representations
• The 2-closure of a \(\frac{3}{2}\)-transitive group in polynomial time
• The Finite Simple Groups
• Two-closure of odd permutation group in polynomial time

Cited in

(9)

• The 2-closure of a \(\frac{3}{2}\)-transitive group in polynomial time
• The 3-closure of a solvable permutation group is solvable
• The closures of wreath products in product action
• Two-closure of odd permutation group in polynomial time
• On finite totally \(2\)-closed groups
• On 2-closed abelian permutation groups
• Closures of finite permutation groups
• On computing the closures of solvable permutation groups
• Two-closure of rank \(3\) groups in polynomial time

This page was built for publication: Two-closures of supersolvable permutation groups in polynomial time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q777912)