The 2-Closure of a 32 -Transitive Group in Polynomial Time | Sciact - Система учета научной деятельности ИМ СО РАН

The 2-Closure of a 32 -Transitive Group in Polynomial Time Научная публикация

Журнал

Siberian Mathematical Journal
ISSN: 0037-4466 , E-ISSN: 1573-9260

Вых. Данные

Год: 2019, Том: 60, Номер: 2, Страницы: 279-290 Страниц : 12 DOI: 10.1134/S0037446619020083

Ключевые слова

3/2-homogeneous coherent configuration; 3/2-transitive group; isomorphism of coherent configurations; k-closure of a permutation group; schurian coherent configuration

Авторы

Vasil’ev A.V. ^1,2 , Churikov D.V. ^1,2

Организации

1	Sobolev Institute of Mathematics, Novosibirsk State University, Novosibirsk, Russian Federation
2	Novosibirsk State University

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. © 2019, Pleiades Publishing, Ltd.

Vasil’ev A.V. , Churikov D.V.
The 2-Closure of a 32 -Transitive Group in Polynomial Time
Siberian Mathematical Journal. 2019. V.60. N2. P.279-290. DOI: 10.1134/S0037446619020083 WOS Scopus OpenAlex

Web of science:	WOS:000465640100008
Scopus:	2-s2.0-85064946503
OpenAlex:	W2941397040

БД	Цитирований
Scopus	6
OpenAlex	5
Web of science	5