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

Tuvi Etzion; Alexander Vardy

doi:10.3934/amc.2011.5.161

Article Contents

2011, Volume 5, Issue 2: 161-176. Doi: 10.3934/amc.2011.5.161

This issue Previous Article A geometric proof of the upper bound on the size of partial spreads in $H(4n+1,$q²$)$ Next Article Large constant dimension codes and lexicodes

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

Tuvi Etzion^1, and
Alexander Vardy^2,

1.
Computer Science Department, Technion - Israel Institute of Technology, Haifa, 32000
2.
Department of Electrical and Computer Engineering, Department of Computer Science and Engineering, Department of Mathematics, University of California San Diego, 9500 Gilman Drive, La Jolla, CA92093

Received: February 28, 2010

Revised: September 30, 2010

Published: April 2011

Abstract Related Papers Cited by

Abstract

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$₂ 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$₂$(5,3,2) = 27$ and $\mathcal C$₂$(7,3,2) \leq 399$. Tables of upper and lower bounds on $\mathcal C$₂$(n,k,r)$ are given for all $n \leq 8$.

Keywords:

Mathematics Subject Classification: Primary: 51E10, 05B40; Secondary: 94B25.

Citation:

Related Papers

Cited by

References

[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 SL_m$(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.