Premium
Graph decompositions in projective geometries
Author(s) -
Buratti Marco,
Nakić Anamari,
Wassermann Alfred
Publication year - 2021
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/jcd.21761
Subject(s) - mathematics , combinatorics , vertex (graph theory) , conjecture , projective space , graph , discrete mathematics , finite field , subspace topology , projective test , pure mathematics , mathematical analysis
Let PG ( F q v ) be the ( v − 1 ) ‐dimensional projective space over F q and let Γ be a simple graph of orderq k − 1 q − 1for some k . A 2 − ( v , Γ , λ )design over F q is a collection ℬ of graphs ( blocks ) isomorphic to Γ with the following properties: the vertex set of every block is a subspace of PG ( F q v ) ; every two distinct points of PG ( F q v ) are adjacent in exactly λ blocks. This new definition covers, in particular, the well‐known concept of a 2 − ( v , k , λ )design over F q 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 F 2 or F 3 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 λ = 1 , that is, the Steiner 2‐designs over a finite field. Also, we briefly touch the new topic of near resolvable 2 − ( v , 2 , 1 ) designs over F q . 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.