Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userNew refiners for permutation group search
58
0
0.0
(
0
)
Added by
Markus Pfeiffer
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We describe how orbital graphs can be used to improve the practical performance of many algorithms for permutation groups, including intersection and stabilizer problems. First we explain how orbital graphs can be integrated in partition backtracking, the current state of the art algorithm for many permutation group problems. We then show how our algorithms perform in practice, demonstrating improvements of several orders of magnitude for some problems.
rate research
Read More
A cycle base of a permutation group is defined to be a maximal set of its pairwise non-conjugate regular cyclic subgroups. It is proved that a cycle base of a permutation group of degree $n$ can be constructed in polynomial time in~$n$.
The $2$-closure $overline{G}$ of a permutation group $G$ on $Omega$ is defined to be the largest permutation group on $Omega$, having the same orbits on $OmegatimesOmega$ as $G$. It is proved that if $G$ is supersolvable, then $overline{G}$ can be found in polynomial time in $|Omega|$. As a byproduct of our technique, it is shown that the composition factors of $overline{G}$ are cyclic or alternating of prime degree.
Let $m$ be a positive integer and let $Omega$ be a finite set. The $m$-closure of $Gleqoperatorname{Sym}(Omega)$ is the largest permutation group on $Omega$ having the same orbits as $G$ in its induced action on the Cartesian product $Omega^m$. The $1$-closure and $2$-closure of a solvable permutation group need not be solvable. We prove that the $m$-closure of a solvable permutation group is always solvable for $mgeq3$.
A marked free monoid morphism is a morphism for which the image of each generator starts with a different letter, and immersions are the analogous maps in free groups. We show that the (simultaneous) PCP is decidable for immersions of free groups, and provide an algorithm to compute bases for the sets, called equalisers, on which the immersions take the same values. We also answer a question of Stallings about the rank of the equaliser. Analogous results are proven for marked morphisms of free monoids.
We show that, there exists a constant $a$ such that, for every subgroup $H$ of a finite group $G$, the number of maximal subgroups of $G$ containing $H$ is bounded above by $a|G:H|^{3/2}$. In particular, a transitive permutation group of degree $n$ has at most $an^{3/2}$ maximal systems of imprimitivity. When $G$ is soluble, generalizing a classic result of Tim Wall, we prove a much stroger bound, that is, the number of maximal subgroups of $G$ containing $H$ is at most $|G:H|-1$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
