Separating rank 3 graphs (Q6171504): Difference between revisions

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