\mathbf{2}-Closure of \mathbf{\frac{3}{2}}-transitive group in polynomial time

DOI10.1134/S0037446619020083arXiv1810.12055MaRDI QIDQ6308917FDOQ6308917

Authors: Andrey Vasil'ev, D. V. Churikov 

Publication date: 29 October 2018

Abstract: Let $G$ be a permutation group on a finite set $Omega$. The $k$-closure $G^{(k)}$ of the group $G$ is the largest subgroup of $operatornameSym(Omega)$ having the same orbits as $G$ on the $k$-th Cartesian power $Omeg{a}^k$ of $Omega$. A group $G$ is called $frac32$-transitive if its transitive and the orbits of a point stabilizer $G_{a}lpha$ on the set $Omegasetminusalpha$ are of the same size greater than one. We prove that the $2$-closure $G^{(2)}$ of a $frac32$-transitive permutation group $G$ can be found in polynomial time in size of $Omega$. In addition, if the group $G$ is not $2$-transitive, then for every positive integer $k$ its $k$-closure can be found within the same time. Applying the result, we prove the existence of a polynomial-time algorithm for solving the isomorphism problem for schurian $frac32$-homogeneous coherent configurations, that is the configurations naturally associated with $frac32$-transitive groups.

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Multiply transitive finite groups (20B20)

This page was built for publication: $\mathbf{2}$-Closure of $\mathbf{\frac{3}{2}}$-transitive group in polynomial time

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