On the Saxl graph of a permutation group

DOI10.1017/S0305004118000610MaRDI QIDQ5216084zbMATH OpenWikidataFDO

Authors Timothy C. Burness, Michael Giudici

Publication date 14 February 2020

Published in Mathematical Proceedings of the Cambridge Philosophical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1712.03688

zbMATH Keywords

base of a permutation groupcombinatorial propertiesprimitive permutation groupSaxl graph

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Primitive groups (20B15) Subgroups of symmetric groups (20B35)

Abstract: 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.

Recommendations

• On the Saxl graphs of primitive groups with soluble stabilisers
• Bases for primitive permutation groups and a conjecture of Babai
• Saxl graphs of primitive affine groups with sporadic point stabilizers
• scientific article; zbMATH DE number 1981753
• Permutation group subdegrees and the common divisor graph

Cites work

• A classification of the maximal subgroups of the finite alternating and symmetric groups
• Base size, metric dimension and other invariants of groups and graphs
• Base sizes for \(\mathcal S\)-actions of finite classical groups.
• Base sizes for simple groups and a conjecture of Cameron
• Base sizes for sporadic simple groups.
• Bases for permutation groups and matroids
• Classical Groups, Derangements and Primes
• Enumerating big orbits and an application: \(B\) acting on the cosets of \(Fi_{23}\).
• scientific article; zbMATH DE number 1849958 (Why is no real title available?)
• scientific article; zbMATH DE number 894528 (Why is no real title available?)
• Malnormal subgroups and Frobenius groups: basics and examples. With an appendix by Denis Osin.
• Maximal subgroups of sporadic groups
• Minimum bases for permutation groups: The greedy approximation
• On base sizes for actions of finite classical groups
• On base sizes for algebraic groups
• On base sizes for symmetric groups
• On fixed points of elements in primitive permutation groups.
• On point stabilizers in primitive permutation groups
• On the base size for the symmetric group acting on subsets.
• On the minimal degree of a primitive permutation group
• On the order of uniprimitive permutation groups
• On the orders of primitive groups
• Orbit invariants and an application to the Baby Monster.
• Paley and the Paley Graphs
• PARTITION ACTIONS OF SYMMETRIC GROUPS AND REGULAR BIPARTITE GRAPHS
• Random Permutations: Some Group-Theoretic Aspects
• Regular orbits of sporadic simple groups
• Regular orbits of symmetric and alternating groups
• Simple groups, permutation groups, and probability
• Some Theorems on Abstract Graphs
• The automorphism group of an extraspecial \(p\)-group
• The base size of a primitive diagonal group.
• THE CLIQUE NUMBERS AND CHROMATIC NUMBERS OF CERTAIN PALEY GRAPHS
• The depth of a finite simple group
• The factorization of graphs. II
• The Inclusion Problem for Finite Primitive Permutation Groups
• The Magma algebra system. I: The user language
• The solution of the k(GV) problem.
• Two point stabilisers of partition actions of linear groups

Cited in

(13)

• On base sizes for primitive groups of product type
• On the Saxl graphs of primitive groups with soluble stabilisers
• On valency problems of Saxl graphs
• Finite groups, 2-generation and the uniform domination number
• Base sizes for primitive groups with soluble stabilisers
• Computational group theory. Abstracts from the workshop held August 15--21, 2021 (hybrid meeting)
• Saxl graphs of primitive affine groups with sporadic point stabilizers
• On the Burness-Giudici conjecture
• scientific article; zbMATH DE number 7790332 (Why is no real title available?)
• Base sizes of primitive groups of diagonal type
• Computational group theory. Abstracts from the workshop held June 1--6, 2025
• Obituary: Jan Saxl (1948--2020)
• On the generalised Saxl graphs of permutation groups

Describes a project that uses

Uses Software

• CTblLib
• Magma
• orb
• CTblLib
• GAP
• ATLAS Group Representations
• GitHub

This page was built for publication: On the Saxl graph of a permutation group

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5216084)