Graph decompositions in projective geometries
Buratti M., Nakic A., Wassermann A.
Abstract
Let PG (Formula presented.) be the (Formula presented.) -dimensional projective space over (Formula presented.) and let (Formula presented.) be a simple graph of order (Formula presented.) for some (Formula presented.). A (Formula presented.) design over (Formula presented.) is a collection (Formula presented.) of graphs (blocks) isomorphic to (Formula presented.) with the following properties: the vertex set of every block is a subspace of PG (Formula presented.); every two distinct points of PG (Formula presented.) are adjacent in exactly (Formula presented.) blocks. This new definition covers, in particular, the well-known concept of a (Formula presented.) design over (Formula presented.) corresponding to the case that (Formula presented.) is complete. In this study of a foundational nature we illustrate how difference methods allow us to get concrete nontrivial examples of (Formula presented.) -decompositions over (Formula presented.) or (Formula presented.) for which (Formula presented.) is a cycle, a path, a prism, a generalized Petersen graph, or a Moebius ladder. In particular, we will discuss in detail the special and very hard case that (Formula presented.) is complete and (Formula presented.), that is, the Steiner 2-designs over a finite field. Also, we briefly touch the new topic of near resolvable (Formula presented.) designs over (Formula presented.). This study has led us to some (probably new) collateral problems concerning difference sets. Supported by multiple examples, we conjecture the existence of infinite families of Γ-decompositions over a finite field that can be obtained by suitably labeling the vertices of Γ with the elements of a Singer difference set.