|
This article is cited in 6 scientific papers (total in 6 papers)
The $2$-closure of a $\frac32$-transitive group in polynomial time
A. V. Vasil'evab, D. V. Churikovab a Novosibirsk State University, Novosibirsk, Russia
b Sobolev Institute of Mathematics, Novosibirsk, Russia
Abstract:
Let $G$ be a permutation group on a finite set $\Omega$. The $k$-closure $G^{(k)}$ of $G$ is the largest subgroup of the symmetric group $\mathrm{Sym}\,(\Omega)$ having the same orbits with $G$ on the $k$th Cartesian power $\Omega^k$ of $\Omega$. The group $G$ is called $\frac32$-transitive, if $G$ is transitive and the orbits of a point stabilizer $G_a$ on $\Omega\{a\}$ are of the same size greater than $1$. 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$. Moreover, 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 coherent configurations naturally associated with $\frac32$-transitive groups.
Keywords:
$k$-closure of a permutation group, $\frac32$-transitive group, $\frac32$-homogeneous coherent configuration, schurian coherent configuration, isomorphism of coherent configurations.
Received: 01.10.2018 Revised: 15.11.2018 Accepted: 19.12.2018
Citation:
A. V. Vasil'ev, D. V. Churikov, “The $2$-closure of a $\frac32$-transitive group in polynomial time”, Sibirsk. Mat. Zh., 60:2 (2019), 360–375; Siberian Math. J., 60:2 (2019), 279–290
Linking options:
https://www.mathnet.ru/eng/smj3080 https://www.mathnet.ru/eng/smj/v60/i2/p360
|
Statistics & downloads: |
Abstract page: | 441 | Full-text PDF : | 129 | References: | 58 | First page: | 28 |
|