Graph decompositions in projective geometries

Abstract

Abstract Let PG be the ‐dimensional projective space over and let be a simple graph of order for some . A design over is a collection of graphs ( blocks ) isomorphic to with the following properties: the vertex set of every block is a subspace of PG; every two distinct points of PG are adjacent in exactly blocks. This new definition covers, in particular, the well‐known concept of a design over corresponding to the case that is complete. In this study of a foundational nature we illustrate how difference methods allow us to get concrete nontrivial examples of ‐decompositions over or for which 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 is complete and , that is, the Steiner 2‐designs over a finite field. Also, we briefly touch the new topic of near resolvable designs over . 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.

Locations

• arXiv (Cornell University) - View - PDF
• Journal of Combinatorial Designs - View