Irredundant bases for the symmetric group.

An irredundant base of a group G$G$ acting faithfully on a finite set Γ$\Gamma$ is a sequence of points in Γ$\Gamma$ that produces a strictly descending chain of pointwise stabiliser subgroups in G$G$, terminating at the trivial subgroup. Suppose that G$G$ is Sn$\operatorname{S}_{n}$ or An$\operatorname{A}_{n}$ acting primitively on Γ$\Gamma$, and that the point stabiliser is primitive in its natural action on n$n$ points. We prove that the maximum size of an irredundant base of G$G$ is On$O\left(\sqrt {n}\right)$, and in most cases O(logn)2$O\left((\log n)^2\right)$. We also show that these bounds are best possible. [ABSTRACT FROM AUTHOR]