zbMATH — the first resource for mathematics

On the Saxl graph of a permutation group. (English) Zbl 07167592
Summary: Let \(G\) be a permutation group on a set \(\Omega\). A subset of \(\Omega\) is a base for \(G\) if its pointwise stabiliser in \(G\) is trivial. In this paper we introduce and study an associated graph \(\Sigma(G)\), which we call the Saxl graph of \(G\). The vertices of \(\Sigma(G)\) are the points of \(\Omega\), and two vertices are adjacent if they form a base for \(G\). This graph encodes some interesting properties of the permutation group. We investigate the connectivity of \(\Sigma(G)\) for a finite transitive group \(G\), as well as its diameter, Hamiltonicity, clique and independence numbers, and we present several open problems. For instance, we conjecture that if \(G\) is a primitive group with a base of size 2, then the diameter of \(\Sigma(G)\) is at most 2. Using a probabilistic approach, we establish the conjecture for some families of almost simple groups. For example, the conjecture holds when \(G = S_n\) or \(A_n\) (with \(n > 12\)) and the point stabiliser of \(G\) is a primitive subgroup. In contrast, we can construct imprimitive groups whose Saxl graph is disconnected with arbitrarily many connected components, or connected with arbitrarily large diameter.

20B35 Subgroups of symmetric groups
20B05 General theory for finite permutation groups
20B15 Primitive groups
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
Full Text: DOI
[1] Babai, L.On the order of uniprimitive permutation groups. Annals of Math.113 (1981), 553-568. · Zbl 0485.20002
[2] Bailey, R. F. and Cameron, P. J.Base size, metric dimension and other invariants of groups and graphs. Bull. London Math. Soc.43 (2011), 209-242. · Zbl 1220.05030
[3] Blaha, K. D.Minimum bases for permutation groups: the greedy approximation. J. Algorithms13 (1992), 297-306. · Zbl 0746.20003
[4] Bosma, W., Cannon, J. and Playoust, C.The Magma algebra system I: the user language. J. Symbolic Comput.24 (1997), 235-265. · Zbl 0898.68039
[5] Breuer, T. The GAP Character Table Library, Version 1.2.1. GAP package, http://www.math.rwth-aachen.de/ Thomas.Breuer/ctbllib, 2012.
[6] Broere, I., Döman, D. and Ridley, J. N.The clique numbers and chromatic numbers of certain Paley graphs. Quaestiones Math.11 (1988), 91-93. · Zbl 0634.05030
[7] Burness, T. C.On base sizes for actions of finite classical groups. J. London Math. Soc.75 (2007), 545-562. · Zbl 1128.20005
[8] Burness, T. C. and Giudici, M.Classical groups, derangements and primes. Aust. Math. Soc. Lecture Series, vol. 25 (Cambridge University Press, 2016.) · Zbl 1372.11001
[9] Burness, T. C., Guralnick, R. M. and Saxl, J.On base sizes for symmetric groups. Bull. London Math. Soc.43 (2011), 386-391. · Zbl 1222.20002
[10] Burness, T. C., Guralnick, R. M. and Saxl, J.Base sizes for \({\mathcal{S}} \)-actions of finite classical groups. Israel J. Math.199 (2014), 711-756. · Zbl 1321.20002
[11] Burness, T. C., Guralnick, R. M. and Saxl, J.On base sizes for algebraic groups. J. Eur. Math. Soc. (JEMS)19 (2017), 2269-2341. · Zbl 1445.20002
[12] Burness, T. C., Guralnick, R. M. and Saxl, J. Base sizes for geometric actions of finite classical groups. In preparation. · Zbl 1321.20002
[13] Burness, T. C., Liebeck, M. W. and Shalev, A.Base sizes for simple groups and a conjecture of Cameron. Proc. London Math. Soc.98 (2009), 116-162. · Zbl 1179.20002
[14] Burness, T. C., Liebeck, M. W. and Shalev, A.The depth of a finite simple group. Proc. Amer. Math. Soc.146 (2018), 2343-2358. · Zbl 06852825
[15] Burness, T. C., O’Brien, E. A. and Wilson, R. A.. Base sizes for sporadic groups. Israel J. Math.177 (2010), 307-333. · Zbl 1216.20008
[16] Cameron, P. J. Some measures of finite groups related to permutation bases. Preprint, arxiv:1408.0968 (2014).
[17] Cameron, P. J. and Fon-Der-Flaass, D. G.Bases for permutation groups and matroids. European J. Combin.16 (1995), 537-544. · Zbl 0837.05036
[18] Cameron, P. J. and Kantor, W. M.Random permutations: some group-theoretic aspects. Combin. Probab. Comput.2 (1993), 257-262. · Zbl 0823.20002
[19] Dirac, G. A.Some theorems on abstract graphs. Proc. London Math. Soc.2 (1952), 69-81. · Zbl 0047.17001
[20] Dixon, J. D. and Mortimer, B.Permutation Groups (Springer-Verlag, New York1996). · Zbl 0951.20001
[21] Fawcett, J. B. Bases of primitive permutation groups. Ph.D. thesis. University of Cambridge (2013).
[22] Fawcett, J. B.The base size of a primitive diagonal group. J. Algebra375 (2013), 302-321. · Zbl 1287.20004
[23] Fawcett, J. B., Müller, J., O’Brien, E. A. and Wilson, R. A.. Regular orbits of sporadic simple groups. Preprint, arxiv:1801.04561 (2018).
[24] Fawcett, J. B., O’Brien, E. A. and Saxl, J.. Regular orbits of symmetric and alternating groups. J. Algebra458 (2016), 21-52. · Zbl 1395.20006
[25] . GAP - Groups, Algorithms, and Programming, Version 4.8.7 (2017), (http://www.gap-system.org).
[26] Guralnick, R. M. and Magaard, K.On the minimal degree of a primitive permutation group. J. Algebra207 (1998), 127-145. · Zbl 0911.20003
[27] Halasi, Z.On the base size for the symmetric group acting on subsets. Studia Sci. Math. Hungar.49 (2012), 492-500. · Zbl 1296.20002
[28] De La Harpe, P. and Weber, C.. Malnormal subgroups and Frobenius groups: basics and examples, with an appendix by Osin, D.. Confluentes Math.6 (2014), 65-76. · Zbl 1327.20030
[29] James, J. P.Two point stabilisers of partition actions of linear groups. J. Algebra297 (2006), 453-469. · Zbl 1156.20314
[30] James, J. P.Partition actions of symmetric groups and regular bipartite graphs. Bull. London Math. Soc.38 (2006), 224-232. · Zbl 1159.20003
[31] James, J. P. Two point stabilisers of partition actions of symmetric, alternating and linear groups. Ph.D. thesis. University of Cambridge (2006).
[32] Jones, G. A. Paley and the Paley graphs. Preprint, arxiv:1702.00285 (2017).
[33] Liebeck, M. W., Praeger, C. E. and Saxl, J.A classification of the maximal subgroups of the finite alternating and symmetric groups. J. Algebra111 (1987), 365-383. · Zbl 0632.20011
[34] Liebeck, M. W and Saxl, J.. On point stabilizers in primitive permutation groups. Comm. Algebra19 (1991), 2777-2786. · Zbl 0731.20003
[35] Liebeck, M. W. and Shalev, A.Simple groups, permutation groups, and probability. J. Amer. Math. Soc.12 (1999), 497-520. · Zbl 0916.20003
[36] Liebeck, M. W. and Shalev, A.On fixed points of elements in primitive permutation groups. J. Algebra421 (2015), 438-459. · Zbl 1309.20001
[37] Lovász, L.The factorization of graphs. In: Combinatorial Structures and their Applications (Gordon and Breach, New York, 1970), 243-246. · Zbl 0247.05155
[38] Maróti, A.On the orders of primitive groups. J. Algebra258 (2002), 631-640. · Zbl 1018.20002
[39] Müller, J., Neunhöffer, M. and Noeske, F. Orb - Methods to enumerate orbits, Version 4.7.6 (2016), (https://github.com/gap-packages/orb/).
[40] Müller, J., Neunhöffer, M. and Wilson, R. A.Enumerating big orbits and an application: B acting on the cosets of Fi_23. J. Algebra314 (2007), 75-96. · Zbl 1134.20007
[41] Neunhöffer, M., Noeske, F., O’Brien, E. A. and Wilson, R.A.. Orbit invariants and an application to the Baby Monster. J. Algebra341 (2011), 297-305. · Zbl 1245.20015
[42] Praeger, C. E.The inclusion problem for finite primitive permutation groups. Proc. London Math. Soc.60 (1990), 68-88. · Zbl 0653.20005
[43] Schmid, P.The solution of the k(GV) problem. ICP Advanced Texts in Mathematics, vol. 4 (Imperial College Press, London, 2007). · Zbl 1153.20001
[44] Seress, Á.. Permutation group algorithms. Cambridge Tracts in Mathematics, vol. 152 (Cambridge University Press, 2003). · Zbl 1028.20002
[45] Wilson, R. A.et al. A World-Wide-Web Atlas of finite group representations. (http://brauer.maths.qmul.ac.uk/Atlas/v3/).
[46] Wilson, R. A.Maximal subgroups of sporadic groups. In: Finite simple groups: thirty years of the atlas and beyond, Contemp. Math. vol. 694 (Amer. Math. Soc., 2017), 57-72.
[47] Winter, D. L.The automorphism group of an extraspecial p-group. Rocky Mountain J. Math.2 (1972), 159-168. · Zbl 0242.20023
[48] Zassenhaus, H.Über endliche Fastkörper. Abh. Math. Sem. Univ. Hamburg11 (1936), 187-220.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.