Bases for primitive permutation groups and a conjecture of Babai (Q1378433): Difference between revisions

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.