On the Ubiquity and Utility of Cyclic Schemes

Abstract

Let $k,l,m,n$, and $\hat{I}¼$ be positive integers. A ${\mathbb{Z}}_{\hat{I}}¼$--{\it scheme of valency} $(k,l)$ and {\it order} $(m,n)$ is a $m\times n$ array $(S_{ij})$ of subsets $S_{ij}\subseteq {\mathbb{Z}}_{\hat{I}}¼$ such that for each row and column one has ${\sum }_{j=1}^n|S_{ij}|=k$ and ${\sum }_{i=1}^m|S_{ij}|=l$, respectively. Any such scheme is an algebraic equivalent of a $(k,l)$-semi-regular bipartite voltage graph with $n$ and $m$ vertices in the bipartition sets and voltages coming from the cyclic group ${\mathbb{Z}}_{\hat{I}}¼$. We are interested in the subclass of ${\mathbb{Z}}_{\hat{I}}¼$--schemes that are characterized by the property $a-b+c-d\not\equiv 0$ (mod $\hat{I}¼$) for all $a\in S_{ij}$, $b\in S_{ih}$, $c\in S_{gh}$, and $d\in S_{gj}$ where $i,g\in 1,...,m$ and $j,h\in 1,...,n$ need not be distinct. These ${\mathbb{Z}}_{\hat{I}}¼$--schemes can be used to represent adjacency matrices of regular graphs of girth $\ge 5$ and semi-regular bipartite graphs of girth $\ge 6$. For suitable $\ddot{I},\ddot{I}ƒ\in \mathbb{N}$ with $\ddot{I}k=\ddot{I}ƒl$, they also represent incidence matrices for polycyclic $(\ddot{I}\hat{I}{¼}_k,\ddot{I}ƒ\hat{I}{¼}_l)$ configurations and, in particular, for all known Desarguesian elliptic semiplanes. Partial projective closures yield {\it mixed ${\mathbb{Z}}_{\hat{I}}¼$-schemes}, which allow new constructions for Krčadinac's sporadic configuration of type $(34_6)$ and Balbuena's bipartite $(q-1)$-regular graphs of girth 6 on as few as $2(q^2-q-2)$ vertices, with $q$ ranging over prime powers. Besides some new results, this survey essentially furnishes new proofs in terms of (mixed) ${\mathbb{Z}}_{\hat{I}}¼$--schemes for ad-hoc constructions used thus far.