Separating rank 3 graphs

DOI10.1016/J.EJC.2023.103732MaRDI QIDQ6171504zbMATH OpenOpenAlexFDO

Authors John Bamberg, Michael Giudici, Jesse Lansdown, Gordon Royle

Publication date 18 July 2023

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

Delsarte boundHoffman boundrank 3 graphsrank 3 primitive groupsseparating graphsseparating groupsstrongly regular graphssynchronising groups

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Group actions on combinatorial structures (05E18) Association schemes, strongly regular graphs (05E30) Primitive groups (20B15)

Abstract: We classify, up to some notoriously hard cases, the rank 3 graphs which fail to meet either the Delsarte or the Hoffman bound. As a consequence, we resolve the question of separation for the corresponding rank 3 primitive groups and give new examples of synchronising, but not $mathbbQmathrmI$, groups of affine type.

Review text

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

Recommendations

• Rank three permutation groups with rank three subconstituents
• CORES OF SYMMETRIC GRAPHS
• Rank 3 transitive decompositions of complete multipartite graphs
• scientific article; zbMATH DE number 1054730
• scientific article; zbMATH DE number 130884
• scientific article; zbMATH DE number 4025470
• On highly regular strongly regular graphs
• On imprimitive rank 3 permutation groups.
• On a class of vertex-transitive distance-regular covers of complete graphs. II
• Finite Homogeneous 3‐Graphs

Cites work

• A classification of one-dimensional affine rank three graphs
• An analogue of the Erdős-Ko-Rado theorem for the distance-regular graphs of bilinear forms
• Between primitive and 2-transitive: synchronization and its friends
• CORES OF SYMMETRIC GRAPHS
• Erdős-Ko-Rado theorems. Algebraic approaches
• Finite Permutation Groups and Finite Simple Groups
• Hoffman's ratio bound
• scientific article; zbMATH DE number 3412859 (Why is no real title available?)
• scientific article; zbMATH DE number 2232233 (Why is no real title available?)
• New non-existence proofs for ovoids of Hermitian polar spaces and hyperbolic quadrics
• On 2-closures of rank 3 groups
• On endomorphisms of alternating forms graph
• On maximal cliques of Cayley graphs over fields
• On Minkowski space and finite geometry
• On the orbit-sizes of permutation groups containing elements separating finite subsets
• Partial ovoids and partial spreads of classical finite polar spaces
• Permutation representations and rational irreducibility
• Pseudo-random properties of self-complementary symmetric graphs
• Strongly regular graphs
• Synchronization and separation in the Johnson schemes
• The Affine Permutation Groups of Rank Three
• The Finite Primitive Permutation Groups of Rank Three
• The Hall-Paige conjecture, and synchronization for affine and diagonal groups
• The Rank 3 Permutation Representations of the Finite Classical Groups
• The structure of finitary permutation groups

Cited in

(7)

• Almost rank three graphs
• A classification of one-dimensional affine rank three graphs
• The subspace structure of maximum cliques in pseudo-Paley graphs from unions of cyclotomic classes
• On the classification of triply transitive strongly regular graphs
• On the twin-width of near-regular graphs
• The non-synchronizing primitive groups of degree up to 624
• Rank three permutation groups with rank three subconstituents

This page was built for publication: Separating rank 3 graphs

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