All about that base

Abstract

This portfolio is comprised of five papers, each concerning base-related invariants of finite permutation groups.

Let Ω be a finite set and G ≤ Sym(Ω). A base for G is a subset B ⊆ Ω such that the pointwise stabiliser G_(B) is trivial. The size of a smallest base for G is denoted b(G). The study of bases originally dates back to the late 19th century but rose to prominence with the advent of computational group theory; as such, the problem of determining b(G) has been of particular interest over the past half-century.

The problem of finding a smallest base for arbitrary finite G is NP-hard, however, there exist polynomial time algorithms to construct relatively small bases. One such algorithm is the greedy algorithm — the size of a largest base it produces for G is denoted 𝒢(G).

The first two papers of the portfolio are concerned with determining b(G) for the symmetric and alternating groups in their natural actions on uniform subsets. In these two papers, two distinct formulas are derived for the base size of such groups, one using primarily combinatorial methods, and the other with a more algebraic approach. The remaining three papers are dedicated to bounding 𝒢(G) for various families of primitive groups G. In particular, we determine 𝒢(G) precisely for all G primitive with sporadic socle, and provide explicit upper bounds for 𝒢(G) when the socle is alternating.

Date of Award	2 Dec 2025
Original language	English
Awarding Institution	University of St Andrews
Supervisor	Colva Roney-Dougal (Supervisor) & Peter Cameron (Supervisor)