On Cameron's Greedy Conjecture

Abstract

A base for a permutation group $G$ acting on a set $\hat{I}\text{c◯}$ is a subset $\mathcal{B}$ of $\hat{I}\text{c◯}$ whose pointwise stabiliser $G_{(\mathcal{B})}$ is trivial. There is a natural greedy algorithm for constructing a base of relatively small size. We write $\mathcal{G}(G)$ the maximum size of a base it produces, and $b(G)$ for the size of the smallest base for $G$. In 1999, Peter Cameron conjectured that there exists an absolute constant $c$ such that every finite primitive group $G$ satisfies $\mathcal{G}(G)\le cb(G)$. We show that if $G$ is ${\mathrm{S}}_n$ or ${\mathrm{A}}_n$ acting primitively then either Cameron's Greedy Conjecture holds for $G$, or $G$ falls into one class of possible exceptions.

21 pages