Two-closures of supersolvable permutation groups in polynomial time

DOI10.1007/S00037-020-00195-7zbMATH Open1484.20002arXiv1912.10217OpenAlexW3037286085MaRDI QIDQ777912FDOQ777912

Andrey Vasil'ev, Ilya Ponomarenko

Publication date: 8 July 2020

Published in: Computational Complexity (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

Cited In (8)

• Two-closure of rank \(3\) groups in polynomial time
• On computing the closures of solvable permutation groups
• The closures of wreath products in product action
• On 2-closed abelian permutation groups
• The 3-closure of a solvable permutation group is solvable
• Closures of finite permutation groups
• On finite totally \(2\)-closed groups
• Two-closure of odd permutation group 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)