TY - JOUR

T1 - Subgroups of minimal index in polynomial time

AU - Skresanov, Saveliy V.

PY - 2020/1/1

Y1 - 2020/1/1

N2 - By applying an old result of Y. Berkovich, we provide a polynomial-time algorithm for computing the minimal possible index of a proper subgroup of a finite permutation group G. Moreover, we find that subgroup explicitly and within the same time if G is given by a Cayley table. As a corollary, we get an algorithm for testing whether or not a finite permutation group acts on a tree non-trivially.

AB - By applying an old result of Y. Berkovich, we provide a polynomial-time algorithm for computing the minimal possible index of a proper subgroup of a finite permutation group G. Moreover, we find that subgroup explicitly and within the same time if G is given by a Cayley table. As a corollary, we get an algorithm for testing whether or not a finite permutation group acts on a tree non-trivially.

KW - group representability on trees

KW - group representability problem

KW - minimal permutation representation

KW - permutation group algorithms

KW - Subgroup of minimal index

KW - FINITE

UR - http://www.scopus.com/inward/record.url?scp=85060685589&partnerID=8YFLogxK

U2 - 10.1142/S0219498820500103

DO - 10.1142/S0219498820500103

M3 - Article

AN - SCOPUS:85060685589

VL - 19

JO - Journal of Algebra and its Applications

JF - Journal of Algebra and its Applications

SN - 0219-4988

IS - 1

M1 - 2050010

ER -