RUS  ENG
Full version
JOURNALS // Sibirskii Matematicheskii Zhurnal // Archive

Sibirsk. Mat. Zh., 2019 Volume 60, Number 2, Pages 360–375 (Mi smj3080)

This article is cited 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.

UDC: 512.542.7

Received: 01.10.2018
Revised: 15.11.2018
Accepted: 19.12.2018

DOI: 10.33048/smzh.2019.60.208


 English version:
Siberian Mathematical Journal, 2019, 60:2, 279–290

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024