Standard

The 2-Closure of a 32 -Transitive Group in Polynomial Time. / Vasil’ev, A. V.; Churikov, D. V.

In: Siberian Mathematical Journal, Vol. 60, No. 2, 01.03.2019, p. 279-290.

Research output: Contribution to journalArticlepeer-review

Harvard

APA

Vancouver

Vasil’ev AV, Churikov DV. The 2-Closure of a 32 -Transitive Group in Polynomial Time. Siberian Mathematical Journal. 2019 Mar 1;60(2):279-290. doi: 10.1134/S0037446619020083

Author

Vasil’ev, A. V. ; Churikov, D. V. / The 2-Closure of a 32 -Transitive Group in Polynomial Time. In: Siberian Mathematical Journal. 2019 ; Vol. 60, No. 2. pp. 279-290.

BibTeX

@article{87c06702b88d4595a5dd027fb00f4452,
title = "The 2-Closure of a 32 -Transitive Group in Polynomial Time",
abstract = " 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. ",
keywords = "3/2-homogeneous coherent configuration, 3/2-transitive group, isomorphism of coherent configurations, k-closure of a permutation group, schurian coherent configuration",
author = "Vasil{\textquoteright}ev, {A. V.} and Churikov, {D. V.}",
year = "2019",
month = mar,
day = "1",
doi = "10.1134/S0037446619020083",
language = "English",
volume = "60",
pages = "279--290",
journal = "Siberian Mathematical Journal",
issn = "0037-4466",
publisher = "MAIK NAUKA/INTERPERIODICA/SPRINGER",
number = "2",

}

RIS

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 -

ID: 20030808