Separating rank 3 graphs (Q6171504): Difference between revisions
From MaRDI portal
Latest revision as of 19:08, 1 August 2024
scientific article; zbMATH DE number 7713634
Language | Label | Description | Also known as |
---|---|---|---|
English | Separating rank 3 graphs |
scientific article; zbMATH DE number 7713634 |
Statements
Separating rank 3 graphs (English)
0 references
18 July 2023
0 references
A transitive finite permutation group has rank 3 if it has exactly three orbits for its action on ordered pairs. A rank 3 graph is a finite graph that can be constructed as the orbital graph of a transitive rank 3 group with also three orbits on unordered pairs (edges and non-edges are defined by the two non-diagonal orbits). Such graphs are strongly regular. Therefore, let $\varGamma$ be a rank 3 graph with vertex set $V(\varGamma)$, maximum clique size $\omega(\varGamma)$ and maximum coclique size $\alpha(\varGamma)$. We have that $\alpha(\varGamma)\omega(\varGamma)\leq|V(\varGamma)|$. Recalling \textit{P. M. Neumann}'s separation theorem for transitive finite permutation groups [Arch. Math. 27, 3--17 (1976; Zbl 0324.20037)], $\varGamma$ is said to be separating if the product $\alpha(\varGamma)\omega(\varGamma)$ is strictly less than $|V(\varGamma)|$. The main purpose of this paper is a classification of the separating rank 3 graphs. It is achieved in detail by the authors, up to some notoriously hard cases. Each of the unresolved cases actually links to some open problems in finite geometry and graph theory: they concern ovoids of finite polar spaces and Peisert graphs. Separation belongs also to a hierarchy of properties involving transitive finite permutation groups: \[ \mathbb{Q}I\Rightarrow\text{ spreading }\Rightarrow\text{ separating }\Rightarrow\text{ synchronising }\Rightarrow\text{ primitive}.\tag{H} \] A group $G$ is separating if and only if every non-trivial $G$-invariant graph is separating. In particular, for a group $G$ of rank 3, $G$ is separating if and only if its corresponding rank 3 graph is separating. Determining which primitive groups are separating has been identified as an important problem in [\textit{J. Araújo} et al., EMS Surv. Math. Sci. 4, No. 2, 101--184 (2017; Zbl 1402.68124)]. The classification of the separating rank 3 graphs provided in this paper is obtained from the classification of rank 3 primitive groups [\textit{M. W. Liebeck} and \textit{J. Saxl}, Bull. Lond. Math. Soc. 18, 165--172 (1986; Zbl 0586.20003)], a description of the automorphism groups of the rank 3 graphs [\textit{S. V. Skresanov}, Ars Math. Contemp. 21, No. 1, Paper No. 8, 20 p. (2021; Zbl 07435680)] and some general properties of separating groups. As a consequence, one can essentially determine the separating groups of rank 3, modulo notoriously difficult cases. The authors also use their results to deduce more information and new examples related to the hierarchy (H).
0 references
rank 3 graphs
0 references
rank 3 primitive groups
0 references
separating graphs
0 references
separating groups
0 references
strongly regular graphs
0 references
Delsarte bound
0 references
Hoffman bound
0 references
synchronising groups
0 references
0 references