On the Saxl graph of a permutation group

• Published in: Mathematical proceedings of the Cambridge Philosophical Society 2020-03, Vol.168 (2), p.219-248
• Main Authors: BURNESS, TIMOTHY C., GIUDICI, MICHAEL
• Format: Article
• Language: English
• Subjects: Apexes; Graph theory; Permutations; Subgroups
• ISSN: 0305-0041; 1469-8064
• DOI: 10.1017/S0305004118000610

Let G be a permutation group on a set Ω. A subset of Ω is a base for G if its pointwise stabiliser in G is trivial. In this paper we introduce and study an associated graph Σ( G ), which we call the Saxl graph of G . The vertices of Σ( G ) are the points of Ω, 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 Σ( 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 Σ( 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.