Article Contents
Article Contents

# On $q$-analogs of Steiner systems and covering designs

• The $q$-analogs of covering designs, Steiner systems, and Turán designs are studied. It is shown that $q$-covering designs and $q$-Turán designs are dual notions. A strong necessary condition for the existence of Steiner structures (the $q$-analogs of Steiner systems) over $\mathbb F$2 is given. No Steiner structures of strength $2$ or more are currently known, and our condition shows that their existence would imply the existence of new Steiner systems of strength $3$. The exact values of the $q$-covering numbers $\mathcal C$q$(n,k,1)$ and $\mathcal C$q$(n,n-1,r)$ are determined for all $q,n,k,r$. Furthermore, recursive upper and lower bounds on the size of general $q$-covering designs and $q$-Turán designs are presented. Finally, it is proved that $\mathcal C$2$(5,3,2) = 27$ and $\mathcal C$2$(7,3,2) \leq 399$. Tables of upper and lower bounds on $\mathcal C$2$(n,k,r)$ are given for all $n \leq 8$.
Mathematics Subject Classification: Primary: 51E10, 05B40; Secondary: 94B25.

 Citation:

•  [1] R. Ahlswede, H. K. Aydinian and L. H. Khachatrian, On perfect codes and related concepts, Des. Codes Crypt., 22 (2001), 221-237.doi: 10.1023/A:1008394205999. [2] M. Braun, A. Kerber and R. Laue, Systematic construction of $q$-analogs of $t$-$(v,k,\lambda)$-designs, Des. Codes Crypt., 34 (2005), 55-70.doi: 10.1007/s10623-003-4194-z. [3] T. Bu, Partitions of a vector space, Disc. Math., 31 (1980), 79-83.doi: 10.1016/0012-365X(80)90174-0. [4] D. de Caen, Extension of a theorem of Moon and Moser on complete subgraphs, Ars Combinatoria, 16 (1983), 5-10. [5] D. de Caen, The current status of Turán's problem on hypergraphs, in "Extremal Problems for Finite Sets'' (eds. P. Frankl, Z. Füredi, G. Katona and D. Miklós), János Bolyai Mathematical Society, Budapest, (1991), 187-197. [6] C. J. Colbourn and R. Mathon, Steiner systems, in "Handbook of Combinatorial Designs'' (eds. C.J. Colbourn and J.H. Dinitz), CRC Press, Boca Raton, FL, (2007), 102-110. [7] T. Etzion, Perfect byte-correcting codes, IEEE Trans. Inform. Theory, 44 (1998), 3140-3146.doi: 10.1109/18.737544. [8] T. Etzion and A. Vardy, Error-correcting codes in projective space, IEEE Trans. Inform. Theory, 57 (2011), 1165-1173.doi: 10.1109/TIT.2010.2095232. [9] S. J. Hong and A. M. Patel, A general class of maximal codes for computer applications, IEEE Trans. Comput., 21 (1972), 1322-1331.doi: 10.1109/T-C.1972.223503. [10] T. Itoh, A new family of $2$-designs over GF$(q)$ admitting SLm$(q^l)$, Geom. Dedicata, 69 (1998), 261-286.doi: 10.1023/A:1005057610394. [11] R. Koetter and F. R. Kschischang, Coding for errors and erasures in random network coding, IEEE Trans. Inform. Theory, 54 (2008), 3579-3591.doi: 10.1109/TIT.2008.926449. [12] A. Kohnert and S. Kurz, Construction of large constant dimension codes with a prescribed minimum distance, Lect. Notes Comput. Sci., 5393 (2008), 31-42.doi: 10.1007/978-3-540-89994-5_4. [13] J. H. van Lint and R. M. Wilson, "A Course in Combinatorics,'' Cambridge University Press, 1992. [14] M. Miyakawa, A. Munemasa and S. Yoshiara, On a class of small $2$-designs over GF$(q)$, J. Combin. Des., 3 (1995), 61-77.doi: 10.1002/jcd.3180030108. [15] J. Schönheim, On coverings, Pacific J. Math., 14 (1964), 1405-1411. [16] M. Schwartz and T. Etzion, Codes and anticodes in the Grassman graph, J. Combin. Theory Ser. A, 97 (2002), 27-42.doi: 10.1006/jcta.2001.3188. [17] H. Suzuki, $2$-designs over GF$(2^m)$, Graphs Combin., 6 (1990), 293-296.doi: 10.1007/BF01787580. [18] H. Suzuki, $2$-designs over GF$(q)$, Graphs Combin., 8 (1992), 381-389.doi: 10.1007/BF02351594. [19] S. Thomas, Designs over finite fields, Geom. Dedicata, 21 (1987), 237-242. [20] S. Thomas, Designs and partial geometries over finite fields, Geom. Ded., 63 (1996), 247-253.doi: 10.1007/BF00181415.