Browse issues
no. 4
The base size of the symmetric group acting on subsets
del Valle, Coen1; Roney-Dougal, Colva M.1
1 School of Mathematics and Statistics University of St Andrews St Andrews UK
Algebraic Combinatorics, Volume 7 (2024) no. 4, pp. 959-967.

A base for a permutation group G acting on a set Ω is a subset ℬ of Ω such that the pointwise stabiliser G (ℬ) is trivial. Let n and r be positive integers with n>2r. The symmetric and alternating groups S n and A n admit natural primitive actions on the set of r-element subsets of {1,2,⋯,n}. Building on work of Halasi [8], we provide explicit expressions for the base sizes of all of these actions, and hence determine the base size of all primitive actions of S n and A n .

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/alco.370
Classification: 20B15, 20B30, 05E16
Keywords: Symmetric group, base size, hypergraph

del Valle, Coen 1; Roney-Dougal, Colva M. 1

1 School of Mathematics and Statistics University of St Andrews St Andrews UK
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{ALCO_2024__7_4_959_0,
     author = {del Valle, Coen and Roney-Dougal, Colva M.},
     title = {The base size of the symmetric group  acting on subsets},
     journal = {Algebraic Combinatorics},
     pages = {959--967},
     publisher = {The Combinatorics Consortium},
     volume = {7},
     number = {4},
     year = {2024},
     doi = {10.5802/alco.370},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.370/}
}
TY  - JOUR
AU  - del Valle, Coen
AU  - Roney-Dougal, Colva M.
TI  - The base size of the symmetric group  acting on subsets
JO  - Algebraic Combinatorics
PY  - 2024
SP  - 959
EP  - 967
VL  - 7
IS  - 4
PB  - The Combinatorics Consortium
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.370/
DO  - 10.5802/alco.370
LA  - en
ID  - ALCO_2024__7_4_959_0
ER  - 
%0 Journal Article
%A del Valle, Coen
%A Roney-Dougal, Colva M.
%T The base size of the symmetric group  acting on subsets
%J Algebraic Combinatorics
%D 2024
%P 959-967
%V 7
%N 4
%I The Combinatorics Consortium
%U https://alco.centre-mersenne.org/articles/10.5802/alco.370/
%R 10.5802/alco.370
%G en
%F ALCO_2024__7_4_959_0
del Valle, Coen; Roney-Dougal, Colva M. The base size of the symmetric group  acting on subsets. Algebraic Combinatorics, Volume 7 (2024) no. 4, pp. 959-967. doi : 10.5802/alco.370. https://alco.centre-mersenne.org/articles/10.5802/alco.370/

[1] Behrens, Sarah; Erbes, Catherine; Ferrara, Michael; Hartke, Stephen G.; Reiniger, Benjamin; Spinoza, Hannah; Tomlinson, Charles New results on degree sequences of uniform hypergraphs, Electron. J. Combin., Volume 20 (2013) no. 4, Paper no. 14, 18 pages | DOI | MR | Zbl

[2] Blaha, Kenneth D. Minimum bases for permutation groups: the greedy approximation, J. Algorithms, Volume 13 (1992) no. 2, pp. 297-306 | DOI | MR | Zbl

[3] Boutin, Debra L. Identifying graph automorphisms using determining sets, Electron. J. Combin., Volume 13 (2006) no. 1, Paper no. 78, 12 pages | DOI | MR | Zbl

[4] Burness, Timothy C.; Guralnick, Robert M.; Saxl, Jan On base sizes for symmetric groups, Bull. Lond. Math. Soc., Volume 43 (2011) no. 2, pp. 386-391 | DOI | MR | Zbl

[5] Burness, Timothy C.; Liebeck, Martin W.; Shalev, Aner Base sizes for simple groups and a conjecture of Cameron, Proc. Lond. Math. Soc. (3), Volume 98 (2009) no. 1, pp. 116-162 | DOI | MR | Zbl

[6] Cáceres, José; Garijo, Delia; González, Antonio; Márquez, Alberto; Puertas, María Luz The determining number of Kneser graphs, Discrete Math. Theor. Comput. Sci., Volume 15 (2013) no. 1, pp. 1-14 | DOI | MR | Zbl

[7] Cameron, Peter J.; Kantor, William M. Random permutations: some group-theoretic aspects, Combin. Probab. Comput., Volume 2 (1993) no. 3, pp. 257-262 | DOI | MR | Zbl

[8] Halasi, Zoltán On the base size for the symmetric group acting on subsets, Studia Sci. Math. Hungar., Volume 49 (2012) no. 4, pp. 492-500 | DOI | MR | Zbl

[9] Liebeck, Martin W.; Shalev, Aner Simple groups, permutation groups, and probability, J. Amer. Math. Soc., Volume 12 (1999) no. 2, pp. 497-520 | DOI | MR | Zbl

[10] Mecenero, Giovanni; Spiga, Pablo A formula for the base size of the symmetric group in its action on subsets, Australas. J. Combin., Volume 88 (2024) no. 2, pp. 244-255 | Zbl

[11] Morris, Joy; Spiga, Pablo On the base size of the symmetric and the alternating group acting on partitions, J. Algebra, Volume 587 (2021), pp. 569-593 | DOI | MR | Zbl

[12] Seress, Ákos Permutation group algorithms, Cambridge Tracts in Mathematics, 152, Cambridge University Press, Cambridge, 2003, x+264 pages | DOI | MR

Cited by Sources: