On relational complexity and base size of finite primitive groups

Veronica Kelsey*, Colva Mary Roney-Dougal

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Downloads (Pure)

Abstract

In this paper we show that if G is a primitive subgroup of Sn that is not large base, then any irredundant base for G has size at most 5 log n. This is the first logarithmic bound on the size of an irredundant base for such groups, and is best possible up to a multiplicative constant. As a corollary, the relational complexity of G is at most 5 log n+1, and the maximal size of a minimal base and the height are both at most 5 log n. Furthermore, we deduce that a base for G of size at most 5 log n can be computed in polynomial time.
Original languageEnglish
Pages (from-to)89–108
JournalPacific Journal of Mathematics
Volume318
Issue number1
DOIs
Publication statusPublished - 1 Aug 2022

Keywords

  • Permutation group
  • Base size
  • Relational complexity
  • Computational complexity

Fingerprint

Dive into the research topics of 'On relational complexity and base size of finite primitive groups'. Together they form a unique fingerprint.

Cite this