The 2-Closure of a \({\textstyle{3 \over 2}}\)-Transitive Group in Polynomial Time

Аннотация

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 \({\textstyle{3 \over 2}}\)-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⁽²⁾ of a \({\textstyle{3 \over 2}}\)-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 \({\textstyle{3 \over 2}}\)-homogeneous coherent configurations, that is coherent configurations naturally associated with \({\textstyle{3 \over 2}}\)-transitive groups.