×

Graph decompositions in projective geometries. (English) Zbl 1536.05045

Summary: Let \(\mathrm{PG}(\mathbb{F}_q^\nu)\) be the \((\nu-1)\)-dimensional projective space over \(\mathbb{F}_q\) and let \(\Gamma\) be a simple graph of order \(\frac{q^k - 1}{q - 1}\) for some \(k\). A \(2\)-\((\nu,\Gamma, \lambda )\) design over \(\mathbb{F}_q\) is a collection \(\mathcal{B}\) of graphs (blocks) isomorphic to \(\Gamma\) with the following properties: the vertex set of every block is a subspace of \(\mathrm{PG}(\mathbb{F}_q^\nu)\); every two distinct points of \(\mathrm{PG}(\mathbb{F}_q^\nu)\) are adjacent in exactly \(\lambda\) blocks. This new definition covers, in particular, the well-known concept of a \(2\)-\((\nu, k, \lambda)\) design over \(\mathbb{F}_q\) corresponding to the case that \(\Gamma\) is complete. In this study of a foundational nature we illustrate how difference methods allow us to get concrete nontrivial examples of \(\Gamma\)-decompositions over \(\mathbb{F}_2\) or \(\mathbb{F}_3\) for which \(\Gamma\) 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 \(\Gamma\) is complete and \(\lambda = 1\), that is, the Steiner 2-designs over a finite field. Also, we briefly touch the new topic of near resolvable \(2\)-\((\nu, 2, 1)\) designs over \(\mathbb{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 \(\Gamma\)-decompositions over a finite field that can be obtained by suitably labeling the vertices of \(\Gamma\) with the elements of a Singer difference set.

MSC:

05B05 Combinatorial aspects of block designs
05B10 Combinatorial aspects of difference sets (number-theoretic, group-theoretic, etc.)
05B25 Combinatorial aspects of finite geometries
05B30 Other designs, configurations
51E20 Combinatorial structures in finite projective spaces
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)

References:

[1] R. J. R.Abel and M.Buratti, Difference families, Handbook of Combinatorial Designs (C. J.Colbourn (ed.) and J. H.Dinitz (ed.), eds.), 2nd ed., Chapman & Hall/CRC, Boca Raton, FL, 2006, pp. 392-410.
[2] R. D.Baker, Partitioning the planes of AG \(( 2 m , 2 )\) into 2‐designs, Discrete Math. 15 (1976), 205-211. · Zbl 0326.05013
[3] T.Beth, D.Jungnickel, and H.Lenz, Design theory, Cambridge University Press, Cambridge, 1999. · Zbl 0945.05005
[4] M.Braun, T.Etzion, P. R. J.Östergård, A.Vardy, and A.Wassermann, On the existence of \(q\)‐analogs of Steiner systems, Forum Math. 4 (2016. · Zbl 1372.51003
[5] M.Braun, A.Kerber, and R.Laue, Systematic construction of \(q\)‐analogs of designs, Des. Codes Cryptogr. 34 (2005), 55-70. · Zbl 1055.05009
[6] M.Braun, M.Kiermaier, and A.Nakić, On the automorphism group of a binary \(q\)‐analog of the Fano plane, European J. Combin. 51 (2016), 443-457. · Zbl 1321.05017
[7] M.Braun, M.Kiermaier, and A.Wassermann, \(q\)‐Analogs of designs: Subspace designs, Chapter in Network Coding and Subspace Designs, Springer, 2018.
[8] M.Braun, M.Kiermaier, and A.Wassermann, Computational methods in subspace designs, Chapter in Network Coding and Subspace Designs (M.Greferath (ed.), M. O.Pavčević (ed.), N.Silberstein (ed.), M. Á.Vázquez‐Castro (ed.), eds.), Springer International Publishing, 2018.
[9] D.Bryant and S.El‐Zanati, Graph decompositions, Handbook of Combinatorial Designs (C. J.Colbourn (ed.) and J. H.Dinitz (ed.), eds.), 2nd ed., Chapman & Hall/CRC, Boca Raton, FL, 2006, pp. 477-486.
[10] M.Buratti, Recursive constructions for difference matrices and relative difference families, J. Combin. Des. 6 (1998), 165-182. · Zbl 0915.05013
[11] M.Buratti, On disjoint \(( v , k , k - 1 )\) difference families, Des. Codes Cryptogr. 87 (2019), 745-755. · Zbl 1407.05037
[12] M.Buratti, S.Capparelli, F.Merola, G.Rinaldi, and T.Traetta, A collection of results on Hamiltonian cycle systems with a nice automorphism group, Electron. Notes Discrete Math. 40 (2013), 245-252.
[13] M.Buratti and L.Gionfriddo, Strong difference families over arbitrary groups, J. Combin. Des. 16 (2008), 443-461. · Zbl 1182.05016
[14] M.Buratti, M.Kiermaier, S.Kurz, A.Nakić, and A.Wassermann, \(q\)‐Analogs of group divisible designs, Combinatorics and Finite Fields: Difference Sets, Polynomials, Pseudorandomness and Applications. Radon Series on Computational and Applied Mathematics (K.‐U.Schmidt (ed.), and A.Winterhof (ed.), eds.), De Gruyter, Berlin. · Zbl 1448.51005
[15] M.Buratti and A.Pasotti, Graph decompositions with the use of difference matrices, Bull. Inst. Combin. Appl. 47 (2006), 23-32. · Zbl 1107.05072
[16] M.Buratti and A.Pasotti, On perfect \(\operatorname{\Gamma} \)‐decompositions of the complete graph, J. Combin. Des. 17 (2009), 197-209. · Zbl 1214.05113
[17] M.Buratti and A.Pasotti, Combinatorial designs and the theorem of Weil on multiplicative character sums, Finite Fields Appl. 15 (2009), 332-344. · Zbl 1211.05022
[18] M.Buratti and A.Nakić, Designs over finite fields by difference methods, Finite Fields Appl. 57 (2019), 128-138. · Zbl 1448.05020
[19] P.Cameron, Generalisation of Fisher’s inequality to fields with more than one element, Combinatorics: Proceedings of the British Combinatorial Conference 1973, London Mathematical Society Lecture Notes Series (T. P.McDonough (ed.), and V. C.Mavron (ed.), eds.), Cambridge University Press, Cambridge, 1974, pp. 9-13. · Zbl 0298.05018
[20] P.Cameron, Locally symmetric designs, Geom. Dedicata3 (1974), 56-76. · Zbl 0284.05014
[21] A.Ćustić, V.Krčadinac, and Y.Zhou, Tiling groups with difference sets, Electron. J. Combin. 22 (2015), 13. · Zbl 1327.05039
[22] P.Delsarte, Association schemes and \(t\)‐designs in regular semilattices, J. Combin. Theory Ser. A20 (1976), 230-243. · Zbl 0342.05020
[23] R.Fuji‐Hara, M.Jimbo, and S.Vanstone, Some results on the line partitioning problem in PG \(( 2 k , q )\), Util. Math. 30 (1986), 235-241. · Zbl 0632.05020
[24] R.Fuji‐Hara, A.Munemasa, and V.Tonchev, Hyperplane partitions and difference systems of sets, J. Combin. Theory Ser. A113 (2006), 1689-1698. · Zbl 1130.05011
[25] J. A.Gallian, A dynamic survey of graph labeling, Electron. J. Combin. 14 (2007), #DS6. · Zbl 0953.05067
[26] P. L.Hammer, U. N.Peled, and X.Sun, Difference graphs, Discrete Appl. Math. 28 (1990), 35-44. · Zbl 0716.05032
[27] M.Hladnik, D.Marušić, and T.Pisanski, Cyclic Haar graphs, Discrete Math. 244 (2002), 137-152. · Zbl 0993.05084
[28] D.Jungnickel, A.Pott, and K. W.Smith, Difference sets, Handbook of Combinatorial Designs (C. J.Colbourn (ed.) and J. H.Dinitz (ed.), eds.), 2nd ed., Chapman & Hall/CRC, Boca Raton, FL, 2006, pp. 419-435.
[29] M.Kiermaier, S.Kurz, and A.Wassermann, The order of the automorphism group of a binary q‐analog of the Fano plane is at most two, Des. Codes Cryptogr. 86 (2018), 239-250. · Zbl 1394.51002
[30] M.Lavrauw and G.Van de Voorde, Field reduction and linear sets in finite geometry, Contemporary Mathematics (G.Kyureghyan (ed.), G.Mullen (ed.), and A.Pott (ed.), eds.), American Mathematical Society, Providence, RI, USA2015, pp. 271-293. · Zbl 1351.51008
[31] R.Mathon, Constructions for cyclic Steiner 2‐designs, Ann. Discrete Math. 34 (1987), 353-362. · Zbl 0647.05015
[32] A.Nakić and M.Pavčević, Tactical decompositions of designs over finite fields, Des. Codes Cryptogr. 77 (2015), 49-60. · Zbl 1328.05020
[33] D. A.Santos, Number theory for mathematical contests, available at https://www.fmf.uni-lj.si/ lavric/Santos
[34] A.Steimle and W.Staton, The isomorphism classes of the generalized Petersen graphs, Discrete Math. 309 (2009), no. 1, 231-237. · Zbl 1219.05098
[35] S.Thomas, Designs over finite fields, Geom. Dedicata24 (1987), 237-242. · Zbl 0627.51013
[36] V.Tonchev, Partitions of difference sets and code synchronization, Finite Fields Appl. 11 (2005), 605-621. · Zbl 1070.05017
[37] R. M.Wilson, Cyclotomy and difference families in elementary abelian groups, J. Number Theory4 (1972), 17-42. · Zbl 0259.05011
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.