Browse issues
no. 3
On the generalised Saxl graphs of permutation groups
Freedman, Saul D.1; Huang, Hong Yi2; Lee, Melissa1; Rekvényi, Kamilla3
1School of Mathematics, Monash University, Clayton VIC 3800, Australia
2Alfréd Rényi Institute of Mathematics, Reáltanoda utca 13-15., H-1053, Budapest, Hungary
3Department of Mathematics, University of Manchester, Manchester, M13 9PL, and Heilbronn Institute for Mathematical Research, Bristol, UK
Algebraic Combinatorics, Volume 9 (2026) no. 3, pp. 611-648

A base for a finite permutation group $G \leqslant \mathrm{Sym}(\Omega )$ is a subset of $\Omega $ with trivial pointwise stabiliser in $G$, and the base size of $G$ is the smallest size of a base for $G$. Motivated by the interest in groups of base size two, Burness and Giudici introduced the notion of the Saxl graph. This graph has vertex set $\Omega $, with edges between elements if they form a base for $G$. We define a generalisation of this graph that encodes useful information about $G$ whenever $b(G) \geqslant 2$: here, the edges are the pairs of elements of $\Omega $ that can be extended to bases of size $b(G)$. In particular, for primitive groups, we investigate the completeness and arc-transitivity of the generalised graph, and the generalisation of Burness and Giudici’s Common Neighbour Conjecture on the original Saxl graph.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/alco.493
Classification: 20B15, 05C25
Keywords: Saxl graph, permutation group, primitive group

Freedman, Saul D.  1 ; Huang, Hong Yi  2 ; Lee, Melissa  1 ; Rekvényi, Kamilla  3

1 School of Mathematics, Monash University, Clayton VIC 3800, Australia
2 Alfréd Rényi Institute of Mathematics, Reáltanoda utca 13-15., H-1053, Budapest, Hungary
3 Department of Mathematics, University of Manchester, Manchester, M13 9PL, and Heilbronn Institute for Mathematical Research, Bristol, UK
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights
Freedman, Saul D.; Huang, Hong Yi; Lee, Melissa; Rekvényi, Kamilla. On the generalised Saxl graphs of permutation groups. Algebraic Combinatorics, Volume 9 (2026) no. 3, pp. 611-648. doi: 10.5802/alco.493
@article{ALCO_2026__9_3_611_0,
     author = {Freedman, Saul D. and Huang, Hong Yi and Lee, Melissa and Rekv\'enyi, Kamilla},
     title = {On the generalised {Saxl} graphs of permutation groups},
     journal = {Algebraic Combinatorics},
     pages = {611--648},
     year = {2026},
     publisher = {The Combinatorics Consortium},
     volume = {9},
     number = {3},
     doi = {10.5802/alco.493},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.493/}
}
TY  - JOUR
AU  - Freedman, Saul D.
AU  - Huang, Hong Yi
AU  - Lee, Melissa
AU  - Rekvényi, Kamilla
TI  - On the generalised Saxl graphs of permutation groups
JO  - Algebraic Combinatorics
PY  - 2026
SP  - 611
EP  - 648
VL  - 9
IS  - 3
PB  - The Combinatorics Consortium
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.493/
DO  - 10.5802/alco.493
LA  - en
ID  - ALCO_2026__9_3_611_0
ER  - 
%0 Journal Article
%A Freedman, Saul D.
%A Huang, Hong Yi
%A Lee, Melissa
%A Rekvényi, Kamilla
%T On the generalised Saxl graphs of permutation groups
%J Algebraic Combinatorics
%D 2026
%P 611-648
%V 9
%N 3
%I The Combinatorics Consortium
%U https://alco.centre-mersenne.org/articles/10.5802/alco.493/
%R 10.5802/alco.493
%G en
%F ALCO_2026__9_3_611_0

[1] Aabrandt, Andreas; Hansen, Vagn Lundsgaard The circle equation over finite fields, Quaest. Math., Volume 41 (2018) no. 5, pp. 665-674 | Zbl | DOI | MR

[2] Arad, Zvi; Chillag, David; Moran, Gadi Groups with a small covering number, Products of conjugacy classes in groups (Lecture Notes in Math.), Volume 1112, Springer, Berlin, 1985, pp. 222-244 | Zbl | DOI | MR

[3] Bailey, Robert F.; Cameron, Peter J. Base size, metric dimension and other invariants of groups and graphs, Bull. Lond. Math. Soc., Volume 43 (2011) no. 2, pp. 209-242 | Zbl | DOI | MR

[4] Bosma, Wieb; Cannon, John; Playoust, Catherine The Magma algebra system. I. The user language, J. Symbolic Comput., Volume 24 (1997) no. 3-4, pp. 235-265 | Zbl | DOI | MR

[5] Bray, John N.; Holt, Derek F.; Roney-Dougal, Colva M. The maximal subgroups of the low-dimensional finite classical groups, London Mathematical Society Lecture Note Series, 407, Cambridge University Press, Cambridge, 2013, xiv+438 pages | DOI | MR | Zbl

[6] Breuer, Thomas The GAP Character Table Library, 2022 https://www.gap-system.org/Packages/ctbllib.html

[7] Breuer, Thomas; Guralnick, Robert M.; Kantor, William M. Probabilistic generation of finite simple groups. II, J. Algebra, Volume 320 (2008) no. 2, pp. 443-494 | DOI | MR | Zbl

[8] Burness, Timothy C. On base sizes for actions of finite classical groups, J. Lond. Math. Soc. (2), Volume 75 (2007) no. 3, pp. 545-562 | DOI | MR | Zbl

[9] Burness, Timothy C. Base sizes for primitive groups with soluble stabilisers, Algebra Number Theory, Volume 15 (2021) no. 7, pp. 1755-1807 | DOI | MR | Zbl

[10] Burness, Timothy C.; Giudici, Michael Classical groups, derangements and primes, Australian Mathematical Society Lecture Series, 25, Cambridge University Press, Cambridge, 2016, xviii+346 pages | Zbl | DOI | MR

[11] Burness, Timothy C.; Giudici, Michael On the Saxl graph of a permutation group, Math. Proc. Cambridge Philos. Soc., Volume 168 (2020) no. 2, pp. 219-248 | Zbl | DOI | MR

[12] Burness, Timothy C.; Huang, Hong Yi On the Saxl graphs of primitive groups with soluble stabilisers, Algebr. Comb., Volume 5 (2022) no. 5, pp. 1053-1087 | DOI | Numdam | Zbl | MR

[13] Burness, Timothy C.; Huang, Hong Yi On base sizes for primitive groups of product type, J. Pure Appl. Algebra, Volume 227 (2023) no. 3, Paper no. 107228, 43 pages | Zbl | DOI | MR

[14] Burness, Timothy C.; O’Brien, E. A.; Wilson, Robert A. Base sizes for sporadic simple groups, Israel J. Math., Volume 177 (2010), pp. 307-333 | Zbl | DOI | MR

[15] Chen, Huye; Du, Shaofei On the Burness-Giudici conjecture, Comm. Algebra, Volume 51 (2023) no. 12, pp. 5019-5045 | Zbl | DOI | MR

[16] Conway, J. H.; Curtis, R. T.; Norton, S. P.; Parker, R. A.; Wilson, R. A. Atlas of finite groups, Oxford University Press, 1985 | Zbl

[17] Coutts, Hannah J.; Quick, Martyn; Roney-Dougal, Colva M. The primitive permutation groups of degree less than 4096, Comm. Algebra, Volume 39 (2011) no. 10, pp. 3526-3546 | Zbl | DOI | MR

[18] Dalla Volta, Francesca; Mastrogiacomo, Fabio; Spiga, Pablo On the cardinality of irredundant and minimal bases of finite permutation groups, J. Algebraic Combin., Volume 60 (2024) no. 2, pp. 569-587 | Zbl | DOI | MR

[19] Dirac, G. A. Some theorems on abstract graphs, Proc. London Math. Soc. (3), Volume 2 (1952), pp. 69-81 | Zbl | DOI | MR

[20] Dixon, John D.; Mortimer, Brian Permutation groups, Graduate Texts in Mathematics, 163, Springer-Verlag, New York, 1996, xii+346 pages | Zbl | DOI | MR

[21] Faradžev, I. A.; Ivanov, A. A. Distance-transitive representations of groups G with PSL 2 (q)⊴G⊴PΓL 2 (q), European J. Combin., Volume 11 (1990) no. 4, pp. 347-356 | Zbl | DOI | MR

[22] Fawcett, Joanna B. The base size of a primitive diagonal group, J. Algebra, Volume 375 (2013), pp. 302-321 | Zbl | DOI | MR

[23] Fawcett, Joanna B. Bases of twisted wreath products, J. Algebra, Volume 607 (2022), pp. 247-271 | Zbl | DOI | MR

[24] GAP – Groups, Algorithms, and Programming, Version 4.12.2 (2022) http://www.gap-system.org

[25] Gill, Nick; Lodà, Bianca; Spiga, Pablo On the height and relational complexity of a finite permutation group, Nagoya Math. J., Volume 246 (2022), pp. 372-411 | Zbl | DOI | MR

[26] Guralnick, Robert M.; Kantor, William M. Probabilistic generation of finite simple groups, J. Algebra, Volume 234 (2000) no. 2, pp. 743-792 | Zbl | DOI | MR

[27] Higman, D. G. Intersection matrices for finite permutation groups, J. Algebra, Volume 6 (1967), pp. 22-42 | Zbl | DOI | MR

[28] Holt, Derek Explicit permutation representation of the Thompson sporadic simple group?, MathOverflow, 2015 https://mathoverflow.net/q/203180

[29] Huang, Hong Yi Base sizes of primitive groups of diagonal type, Forum Math. Sigma, Volume 12 (2024), Paper no. e2, 43 pages | Zbl | DOI | MR

[30] Huang, Hong Yi Bases for permutation groups and related problems, Ph. D. Thesis, University of Bristol (2025)

[31] Huppert, B. Endliche Gruppen. I, Die Grundlehren der mathematischen Wissenschaften, Band 134, Springer-Verlag, Berlin-New York, 1967, xii+793 pages | DOI | Zbl | MR

[32] Kleidman, Peter; Liebeck, Martin The subgroup structure of the finite classical groups, London Mathematical Society Lecture Note Series, 129, Cambridge University Press, Cambridge, 1990, x+303 pages | Zbl | DOI | MR

[33] Lee, Melissa Regular orbits of quasisimple linear groups I, J. Algebra, Volume 586 (2021), pp. 1122-1194 | Zbl | DOI | MR

[34] Lee, Melissa Regular orbits of quasisimple linear groups II, J. Algebra, Volume 586 (2021), pp. 643-717 | Zbl | DOI | MR

[35] Lee, Melissa; Popiel, Tomasz Saxl graphs of primitive affine groups with sporadic point stabilizers, Internat. J. Algebra Comput., Volume 33 (2023) no. 2, pp. 369-389 | Zbl | DOI | MR

[36] Leemans, Dimitri; Liebeck, Martin W. Chiral polyhedra and finite simple groups, Bull. Lond. Math. Soc., Volume 49 (2017) no. 4, pp. 581-592 | Zbl | DOI | MR

[37] Liebeck, Martin W. The affine permutation groups of rank three, Proc. London Math. Soc. (3), Volume 54 (1987) no. 3, pp. 477-516 | Zbl | DOI | MR

[38] Liebeck, Martin W.; Praeger, Cheryl E.; Saxl, Jan On the O’Nan-Scott theorem for finite primitive permutation groups, J. Austral. Math. Soc. Ser. A, Volume 44 (1988) no. 3, pp. 389-396 | DOI | Zbl | MR

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

[40] Lucchini, Andrea; Morigi, Marta; Moscatiello, Mariapia Primitive permutation IBIS groups, J. Combin. Theory Ser. A, Volume 184 (2021), Paper no. 105516, 17 pages | DOI | Zbl | MR

[41] Lucchini, Andrea; Nemmi, Daniele On the connectivity of the generating and rank graphs of finite groups, J. Algebra, Volume 665 (2025), pp. 131-144 | Zbl | DOI | MR

[42] Neunhöffer, Max; Noeske, Felix; O’Brien, E. A.; Wilson, Robert A. Orbit invariants and an application to the Baby Monster, J. Algebra, Volume 341 (2011), pp. 297-305 | Zbl | DOI | MR

[43] Rekvényi, Kamilla On the orbital diameter of groups of diagonal type, J. Combin. Theory Ser. A, Volume 190 (2022), Paper no. 105636, 26 pages | Zbl | DOI | MR

[44] Rekvényi, Kamilla The orbital diameter of primitive permutation groups, Ph. D. Thesis, Imperial College London (2023)

[45] Rekvényi, Kamilla On the orbital diameter of primitive affine groups, Comm. Algebra, Volume 53 (2025) no. 9, pp. 3662-3706 | Zbl | DOI | MR

[46] Sims, Charles C. Computational methods in the study of permutation groups, Computational Problems in Abstract Algebra (Proc. Conf., Oxford, 1967), Pergamon, Oxford-New York-Toronto, Ont., 1970, pp. 169-183 | Zbl | MR

[47] Singerman, David Symmetries of Riemann surfaces with large automorphism group, Math. Ann., Volume 210 (1974), pp. 17-32 | Zbl | DOI | MR

[48] Wilson, Robert; Walsh, Peter; Tripp, Jonathan; Suleiman, Ibrahim; Parker, Richard; Norton, Simon; Nickerson, Simon; Linton, Steve; Bray, John; Abbott, Rachel ATLAS of Finite Group Representations - Version 3 http://atlas.math.rwth-aachen.de/Atlas/v3/

[49] Wilson, Robert A.; Parker, Richard A.; Nickerson, Simon; Bray, John N.; Breuer, Thomas AtlasRep GAP Package, Version 2.1.6, 2022

[50] Wilson, Robert A.; Walsh, Peter; Tripp, Jonathan; Suleiman, Ibrahim; Parker, Richard A.; Norton, Simon; Nickerson, Simon; Linton, Steve; Bray, John N.; Abbott, Rachel ATLAS of Finite Group Representations - Version 2 http://atlas.math.rwth-aachen.de/Atlas/

Cited by Sources: