# 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.

##### MSC:
 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:
##### References:
  Babai, L.On the order of uniprimitive permutation groups. Annals of Math.113 (1981), 553-568. · Zbl 0485.20002  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  Blaha, K. D.Minimum bases for permutation groups: the greedy approximation. J. Algorithms13 (1992), 297-306. · Zbl 0746.20003  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  Breuer, T. The GAP Character Table Library, Version 1.2.1. GAP package, http://www.math.rwth-aachen.de/ Thomas.Breuer/ctbllib, 2012.  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  Burness, T. C.On base sizes for actions of finite classical groups. J. London Math. Soc.75 (2007), 545-562. · Zbl 1128.20005  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  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  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  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  Burness, T. C., Guralnick, R. M. and Saxl, J. Base sizes for geometric actions of finite classical groups. In preparation. · Zbl 1321.20002  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  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  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  Cameron, P. J. Some measures of finite groups related to permutation bases. Preprint, arxiv:1408.0968 (2014).  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  Cameron, P. J. and Kantor, W. M.Random permutations: some group-theoretic aspects. Combin. Probab. Comput.2 (1993), 257-262. · Zbl 0823.20002  Dirac, G. A.Some theorems on abstract graphs. Proc. London Math. Soc.2 (1952), 69-81. · Zbl 0047.17001  Dixon, J. D. and Mortimer, B.Permutation Groups (Springer-Verlag, New York1996). · Zbl 0951.20001  Fawcett, J. B. Bases of primitive permutation groups. Ph.D. thesis. University of Cambridge (2013).  Fawcett, J. B.The base size of a primitive diagonal group. J. Algebra375 (2013), 302-321. · Zbl 1287.20004  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).  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  . GAP - Groups, Algorithms, and Programming, Version 4.8.7 (2017), (http://www.gap-system.org).  Guralnick, R. M. and Magaard, K.On the minimal degree of a primitive permutation group. J. Algebra207 (1998), 127-145. · Zbl 0911.20003  Halasi, Z.On the base size for the symmetric group acting on subsets. Studia Sci. Math. Hungar.49 (2012), 492-500. · Zbl 1296.20002  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  James, J. P.Two point stabilisers of partition actions of linear groups. J. Algebra297 (2006), 453-469. · Zbl 1156.20314  James, J. P.Partition actions of symmetric groups and regular bipartite graphs. Bull. London Math. Soc.38 (2006), 224-232. · Zbl 1159.20003  James, J. P. Two point stabilisers of partition actions of symmetric, alternating and linear groups. Ph.D. thesis. University of Cambridge (2006).  Jones, G. A. Paley and the Paley graphs. Preprint, arxiv:1702.00285 (2017).  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  Liebeck, M. W and Saxl, J.. On point stabilizers in primitive permutation groups. Comm. Algebra19 (1991), 2777-2786. · Zbl 0731.20003  Liebeck, M. W. and Shalev, A.Simple groups, permutation groups, and probability. J. Amer. Math. Soc.12 (1999), 497-520. · Zbl 0916.20003  Liebeck, M. W. and Shalev, A.On fixed points of elements in primitive permutation groups. J. Algebra421 (2015), 438-459. · Zbl 1309.20001  Lovász, L.The factorization of graphs. In: Combinatorial Structures and their Applications (Gordon and Breach, New York, 1970), 243-246. · Zbl 0247.05155  Maróti, A.On the orders of primitive groups. J. Algebra258 (2002), 631-640. · Zbl 1018.20002  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/).  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  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  Praeger, C. E.The inclusion problem for finite primitive permutation groups. Proc. London Math. Soc.60 (1990), 68-88. · Zbl 0653.20005  Schmid, P.The solution of the k(GV) problem. ICP Advanced Texts in Mathematics, vol. 4 (Imperial College Press, London, 2007). · Zbl 1153.20001  Seress, Á.. Permutation group algorithms. Cambridge Tracts in Mathematics, vol. 152 (Cambridge University Press, 2003). · Zbl 1028.20002  Wilson, R. A.et al. A World-Wide-Web Atlas of finite group representations. (http://brauer.maths.qmul.ac.uk/Atlas/v3/).  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.  Winter, D. L.The automorphism group of an extraspecial p-group. Rocky Mountain J. Math.2 (1972), 159-168. · Zbl 0242.20023  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.