Subgroups of minimal index in polynomial time

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish
Article number2050010
Number of pages4
JournalJournal of Algebra and its Applications
Volume19
Issue number1
DOIs
Publication statusPublished - 1 Jan 2020

Keywords

  • group representability on trees
  • group representability problem
  • minimal permutation representation
  • permutation group algorithms
  • Subgroup of minimal index
  • FINITE

Fingerprint

Dive into the research topics of 'Subgroups of minimal index in polynomial time'. Together they form a unique fingerprint.

Cite this