Bases for primitive permutation groups and a conjecture of Babai
type: Item
instance of: scholarly article
title: Bases for primitive permutation groups and a conjecture of Babai
zbMATH Open document ID: 0897.20005
author: David Gluck
author: Ákos Seress
author: Aner Shalev
published in: Journal of Algebra
publication date: 1998-08-06T00:00:00Z
review text: A base for a permutation group \(G\leq S_n\) of degree \(n\) is by definition a sequence \(B=(\beta_1,\ldots,\beta_M)\) of points in \(\Omega\) such that in \(G\) only the identity fixes each point of \(B\); \(M\) is called the size of the base \(B\). Denote by \(\Gamma_d\) the family of all finite groups such that \(G\) has no alternating composition factor of degree \(>d\) and no classical composition factor of rank \(>d\). It is proved in Theorem 1.2 that there exists a function \(g\colon d\mapsto g(d)\) of positive integers such that if \(G\leq S_n\) is primitive and \(G\in\Gamma_d\) then \(G\) has a base of size at most \(g(d)\). Moreover, \(g\) can be chosen as a quadratic function. It is shown that the greedy algorithm can be used to produce such bases. The theorem confirms a conjecture by Babai.
Mathematics Subject Classification ID: 20B15
Mathematics Subject Classification ID: 20D60
zbMATH DE Number: 1117773
zbMATH Keywords: bases
zbMATH Keywords: base sizes
zbMATH Keywords: primitive permutation groups
MaRDI profile type: Publication
OpenAlex ID: W1996938202
Wikidata QID: Q123138859
cites work: On the orders of primitive groups with restricted nonabelian composition factors
cites work: Random Permutations: Some Group-Theoretic Aspects
cites work: On groups with no regular orbits on the set of subsets
cites work: Chains of subgroups in symmetric groups
cites work: Base Sizes and Regular Orbits for Coprime Affine Permutation Groups
cites work: Q5577154
cites work: Generators for Finite Simple Groups, with Applications to Linear Groups
cites work: Q3253828
cites work: Q3791327
cites work: Minimal Degrees of Primitive Permutation Groups, with an Application to Monodromy Groups of Covers of Riemann Surfaces
cites work: Isomorphism of graphs of bounded valence can be tested in polynomial time
cites work: Q4273608
cites work: Q4273611
cites work: Q3907748
cites work: The Minimal Base Size of Primitive Solvable Permutation Groups
cites work: Primitive Groups with no Regular Orbits on the Set of Subsets
cites work: Q5617749
cites work: Q3712472
DOI: 10.1006/JABR.1997.7149
description: scientific article; zbMATH DE number 1117773