The base size of the symmetric group acting on subsets (Q6614049)

A base for a permutation group \(G\) acting on a set \(\Omega\) is a subset of \(\Omega\) such that the pointwise stabilizer in \(G\) of the subset is trivial. The minimal size of a base for \(G\) is denoted by \(b(G)\). In this paper, \(G\) is taken to be the symmetric group \(S_n\) or the alternating group \(A_n\) and \(\Omega\) is the set of \(r\)-element subsets of \(\{ 1, \ldots, n \}\) for any fixed (positive integer) \(r\) less than \(n/2\). In the former case, \(b(G)\) is denoted by \(b(S_{n,r})\) and in the latter case \(b(G)\) is \(b(A_{n,r})\).\N\NIn [Stud. Sci. Math. Hung. 49, No. 4, 492--500 (2012; Zbl 1296.20002)], \textit{Z. Halasi} showed that \(b(S_{n,r}) \geq \lceil \frac{2n-2}{r+1} \rceil\) with equality when \(n \geq r^{2}\) (later improved in [\textit{J. Cáceres} et al., Discrete Math. Theor. Comput. Sci. 15, No. 1, 1--14 (2013; Zbl 1283.05122)] to \(n \geq (r^{2}+r)/2\)) and that \(b(S_{n,r}) \geq \lceil \log_{2}n \rceil\) for all \(n \geq 2r\) with equality if \(n=2r\).\N\NGiven \(l\), \(k\), \(r \in \mathbb{N}\), set \(m_{r}(l,k) = \frac{1}{k} ( lr - \sum_{i=1}^{k-1} i \binom{l}{i} )\). Building on [Halasi, loc. cit.], the authors obtain the following result:\N\NTheorem 1. Let \(n \geq 2r\) be fixed and let \(l\) be minimal such that there exists some \(k \leq l+1\) satisfying \(0 \leq m_{r}(l,k) \leq \binom{l}{k}\) and \(\sum_{i=0}^{k-1} \binom{l}{i} + m_{r}(l,k) \geq n\). Then \(b(S_{n,r}) = b(A_{n+1,r}) = l\).\N\NIn the case of symmetric groups, a result similar to Theorem 1 was independently obtained by \textit{G. Mecenero} and \textit{P. Spiga} [Australas. J. Comb. 88, Part 2, 244--255 (2024; Zbl 1536.20008)]. The two proofs are different.\N\NWe note that the number \(b(S_{n,r})\) is the determining number for the Kneser graph \(K_{n,r}\). (The determining number of a graph \(\Gamma\) with vertex set \(V\) is the minimum cardinality of a subset \(S\) of \(V\) such that the pointwise stabilizer of \(S\) in \(\mathrm{Aut}(\Gamma)\) is trivial. The vertex set of \(K_{n,r}\) is the set of all \(r\)-element subsets in \(\{ 1, \ldots , n \}\) and two subsets are connected by an edge in \(K_{n,r}\) if and only if they are disjoint.)\N\NWe mention a corollary of Theorem 1.\N\NCorollary. For positive integers \(n\) and \(r\) satisfying \(r^{3/2} + (r/2) + 1 \leq n < (r^{2}+r)/2\), one has\N\[\Nb(S_{n,r}) = \Big\lceil {\Big( 3(2n+r - \frac{5}{4}) + r^{2} \Big)}^{1/2} - r - \frac{3}{2} \Big\rceil.\N\]