\documentclass[ALCO,published]{cedram}
\usepackage{dsfont}
\usepackage{float}
\usepackage{enumitem}
\newcommand\A{\mathrm{A}}
\newcommand\one{\mathds{1}}
\newcommand\zero{\mathbf{0}}
\newcommand\vb{\mathbf{b}}
\newcommand\vd{\mathbf{d}}
\newcommand\vf{\mathbf{f}}
\newcommand\vx{\mathbf{x}}
\newcommand\vy{\mathbf{y}}
\newcommand\vz{\mathbf{z}}
\newcommand\F{\mathbb{F}}
\newcommand\C{\mathbb{C}}
\newcommand\Z{\mathbb{Z}}
\newcommand\Q{\mathbb{Q}}
\newcommand\R{\mathbb{R}}
\renewcommand\S{\mathrm{S}}
\newcommand\tr{\mathrm{tr}}
\newcommand\Aut{\mathrm{Aut}}
\newcommand\bal{\mathrm{bal}}
\renewcommand\P{\mathcal{P}}
\newcommand\lam{\lambda}
\newcommand\lcm{\mathrm{lcm}}
\def\dotcup{\,\dot\cup\,}
\newcommand{\ontopof}[2]{\genfrac{}{}{0pt}{}{#1}{#2}}
\newcommand{\comment}[1]{}
\newcommand\aug{\fboxsep=-\fboxrule\!\!\!\fbox{\strut}\!\!\!}
\renewcommand{\theenumi}{\alph{enumi}}
\title[Base size of the symmetric group]{The base size of the symmetric group \\acting on subsets}
\author[\initial{C.} del Valle]{\firstname{Coen} \lastname{del Valle}}
\address{
School of Mathematics and Statistics\\
University of St Andrews\\ St Andrews\\ UK}
\email{cdv1@st-andrews.ac.uk}
\author[\initial{C.} \middlename{M.} Roney-Dougal]{\firstname{Colva} \middlename{M.} \lastname{Roney-Dougal}}
\address{
School of Mathematics and Statistics\\
University of St Andrews\\ St Andrews\\ UK
}
\email{Colva.Roney-Dougal@st-andrews.ac.uk}
\thanks{Research of Coen del Valle is supported by the Natural Sciences and Engineering Research Council of Canada (NSERC), [funding reference number PGSD-577816-2023], as well as a University of St Andrews School of Mathematics and Statistics Scholarship. Both authors thank the referee for their helpful suggestions, which have greatly improved the paper.}
\keywords{Symmetric group, base size, hypergraph}
\subjclass{20B15, 20B30, 05E16}
\datepublished{2024-09-03}
\begin{document}
\date{today}
\begin{abstract}
A base for a permutation group $G$ acting on a set $\Omega$ is a subset $\mathcal{B}$ of $\Omega$ such that the pointwise stabiliser $G_{(\mathcal{B})}$ is trivial. Let $n$ and $r$ be positive integers with $n>2r$. The symmetric and alternating groups $\mathrm{S}_n$ and $\mathrm{A}_n$ admit natural primitive actions on the set of $r$-element subsets of $\{1,2,\dots, n\}$. Building on work of Halasi~\cite{hal}, we provide explicit expressions for the base sizes of all of these actions, and hence determine the base size of all primitive actions of $\mathrm{S}_n$ and $\mathrm{A}_n$.
\end{abstract}
\maketitle
\section{Introduction}
A \emph{base} for a permutation group $G$ acting on a set $\Omega$ is a subset $\{\alpha_1,\alpha_2,\dots, \alpha_k\}\subseteq\Omega$ with trivial pointwise stabiliser in $G$. Bases have proved to be tremendously useful in permutation group algorithms (see e.g.~\cite{ser}); for many computations the complexity is a function of the size of the base used, so it is of interest to find a smallest possible base. The size $b(G)$ of a smallest base for $G$ is called the \emph{base size} of $G$. Blaha~\cite{blaha} shows that for any positive integer $l$, and any permutation group $G$, the problem of determining whether $G$ admits a base of size at most $l$ is NP-complete. On the other hand, there are many different estimates known for $b(G)$ --- for example we can derive elementary upper and lower bounds as follows. If $\{\alpha_i\}_{i=1}^{k}$ is a base for $G$ then any group element $g\in G$ is uniquely determined by the tuple $(\alpha_i^g)_{i=1}^{k}$ and so $|G|\leq |\Omega|^{k}$. If $k=b(G)$ then $|G_{(\alpha_1,\alpha_2,\dots,\alpha_i)} : G_{(\alpha_1,\alpha_2,\dots,\alpha_{i+1})}|\geq 2$ for all $1\leq in\geq r^{3/2}+\frac{r}{2}+1$. Then $$b(\S_{n,r})=\left\lceil\left(3\left(2n+r-\frac{5}{4}\right)+r^2\right)^\frac{1}{2}-r-\frac{3}{2}\right\rceil.$$
\end{coro}
\begin{proof}
Suppose first that there is some base $\mathcal{B}=\{B_1,\dots, B_k\}$ for $\S_{n,r}$ with largest vertex neighbourhood of size at most 2. Then $B_2$ has at least $r-1$ points not in $B_1$, $B_3$ has at least $r-2$ points not in $B_1\cup B_2$, and so on. Thus $$n\geq r+(r-1)+\cdots+1=(r^2+r)/2,$$ a contradiction. Therefore, there is no base for $\S_{n,r}$ with largest neighbourhood size at most 2. Therefore if $\mathcal{B}$ is any base for $\S_{n,r}$ then at least one point has a neighbourhood of size at least three, thus by the discussion following Lemma~\ref{doubcount}, $1+b+\binom{b}{2}+m(b,3)\geq n$. That is, $$n\leq1+b+\binom{b}{2}+\frac{1}{3}(br-b-b(b-1))=\frac{b^2+(2r+3)b}{6}+1,$$ solving for $b$ (e.g. via the quadratic formula) gives $$b\geq\left(3\left(2n+r-\frac{5}{4}\right)+r^2\right)^\frac{1}{2}-r-\frac{3}{2}.$$
The above also shows that if we set $l$ to be (the ceiling of) the quantity above and $k$ to be $3$, then $l$ is the minimum positive integer satisfying $1+l+\binom{l}{2}+m(l,k)\geq n$. Therefore, by Theorem~\ref{minbase} if we can show that $0\leq m(l,k)=\frac{1}{3}(lr-l^2)\leq \binom{l}{3}$, or equivalently that $l\leq r\leq (l^2-l)/2+1$, then $b(\S_{n,r})=l$.
First, $l>r$ implies $(24n+4r^2+12r-15)^{1/2}>4r+3$. Rearranging gives \linebreak$n>(r^2+r+2)/2$, a contradiction, so $l\leq r$. Finally, since $n\geq r^{3/2}+\frac{r}{2}+1$, a straightforward calculation shows that $r\leq (l^2-l)/2+1$, hence the result.
\end{proof}
\begin{rema}
In fact, the result holds for $(r^2+r)/2>n\geq \frac{(8r^3+25r^2+4r-28)^\frac{1}{2}}{6}+\frac{r}{2}+1$ --- the lower bound of $n\geq r^{3/2}+\frac{r}{2}+1$ is used in the statement simply for presentation.
\end{rema}
One could continue to play this game, obtaining explicit formulae for different ranges of $n$, however the calculations quickly become increasingly complicated.
\bibliographystyle{mersenne-plain}
\bibliography{ALCO_del-Valle_1004}
\end{document}