On the existence of self-complementary and non-self-complementary strongly regular graphs with Paley parameters (Q506935): Difference between revisions

The Paley graphs are a well-known class of strongly regular graphs, which are self-complementary. The paper at hand searches for other examples of strongly regular graphs that have the same regularity parameters as Paley. The main goal is to find examples of such graphs which are not self-complementary and which are non-Schurian. The graphs in question are in fact basis graphs of certain association schemes. An association scheme (sometimes called a homogeneous coherent configuration) consists of a set \(V\) and a set of relations \(\{R_{0}, R_{1}, \dots, R_{d}\}\) on \(V\) satisfying the properties: \(R_{0}\) is the identity relation, and the \(R_{i}\) form a partition of \(V \times V\). For any \(0 \leq i \leq d\), there is a \(j\) so that \(R_{i}^{-1} = R_{j}\). For any triple of relations \(R_{i}\), \(R_{j}\), \(R_{k}\), and for any \((x,y) \in R_{k}\), the number \[ p_{i,j}^{k} = \left|\{z \in V \mid (x,z) \in R_{i} \text{ and } (z,y) \in R_{j} \} \right| \] is independent of the choice of \((x,y)\). (These axioms can be phrased algebraically as well, in which case the numbers \(p_{i,j}^{k}\) are the structure constants of the algebra spanned by the matrices representing the \(R_{i}\).) Given an association scheme, one can potentially create other association schemes (called fusion schemes) by taking the union of several of the \(R_{i}\), creating a strictly coarser partition in the first axiom. (Of course, not all such coarser partitions will satisfy the other axioms.) The paper begins with the complete classical affine scheme \(\mathcal{A}_{p}\), built on the data of the classical affine plane of order \(p\). The underlying set \(V\) is \(\mathbb{F}_{p}^{2}\), and the relations are defined using the sets of parallel lines in the affine plane. The rest of the paper is devoted to understanding the fusion schemes of \(\mathcal{A}_{p}\). By carefully examining certain groups that act on \(\mathcal{A}_{p}\) and the resulting orbits on fusion schemes of \(\mathcal{A}_{p}\) with \(d=2\), the authors show the existence of large numbers of complementary and non-self-complementary graphs with Paley parameters. In fact, using Burnside-Polya enumeration to examine the orbits, the authors determine the number of graphs that can be constructed from such fusion schemes of \(\mathcal{A}_{p}\) in this manner, as well as the asymptotic behavior of these numbers as \(p\) grows.