TY - JOUR
T1 - The 2-Closure of a 32 -Transitive Group in Polynomial Time
AU - Vasil’ev, A. V.
AU - Churikov, D. V.
PY - 2019/3/1
Y1 - 2019/3/1
N2 -
Let G be a permutation group on a finite set Ω. The k-closure G
(k)
of G is the largest subgroup of the symmetric group Sym(Ω) having the same orbits with G on the kth Cartesian power Ω
k
of Ω. The group G is called 32-transitive, if G is transitive and the orbits of a point stabilizer G
α
on Ω{α} are of the same size greater than 1. We prove that the 2-closure G
(2)
of a 32-transitive permutation group G can be found in polynomial time in size of Ω. 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 32-homogeneous coherent configurations, that is coherent configurations naturally associated with 32-transitive groups.
AB -
Let G be a permutation group on a finite set Ω. The k-closure G
(k)
of G is the largest subgroup of the symmetric group Sym(Ω) having the same orbits with G on the kth Cartesian power Ω
k
of Ω. The group G is called 32-transitive, if G is transitive and the orbits of a point stabilizer G
α
on Ω{α} are of the same size greater than 1. We prove that the 2-closure G
(2)
of a 32-transitive permutation group G can be found in polynomial time in size of Ω. 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 32-homogeneous coherent configurations, that is coherent configurations naturally associated with 32-transitive groups.
KW - 3/2-homogeneous coherent configuration
KW - 3/2-transitive group
KW - isomorphism of coherent configurations
KW - k-closure of a permutation group
KW - schurian coherent configuration
UR - http://www.scopus.com/inward/record.url?scp=85064946503&partnerID=8YFLogxK
U2 - 10.1134/S0037446619020083
DO - 10.1134/S0037446619020083
M3 - Article
AN - SCOPUS:85064946503
VL - 60
SP - 279
EP - 290
JO - Siberian Mathematical Journal
JF - Siberian Mathematical Journal
SN - 0037-4466
IS - 2
ER -