2011, 5(2): 161-176. doi: 10.3934/amc.2011.5.161

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

1. 

Computer Science Department, Technion - Israel Institute of Technology, Haifa, 32000, Israel

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, United States

Received  March 2010 Revised  October 2010 Published  May 2011

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$.
Citation: Tuvi Etzion, Alexander Vardy. On $q$-analogs of Steiner systems and covering designs. Advances in Mathematics of Communications, 2011, 5 (2) : 161-176. doi: 10.3934/amc.2011.5.161
References:
[1]

R. Ahlswede, H. K. Aydinian and L. H. Khachatrian, On perfect codes and related concepts,, Des. Codes Crypt., 22 (2001), 221. 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. doi: 10.1007/s10623-003-4194-z.

[3]

T. Bu, Partitions of a vector space,, Disc. Math., 31 (1980), 79. 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.

[5]

D. de Caen, The current status of Turán's problem on hypergraphs,, in, (1991), 187.

[6]

C. J. Colbourn and R. Mathon, Steiner systems,, in, (2007), 102.

[7]

T. Etzion, Perfect byte-correcting codes,, IEEE Trans. Inform. Theory, 44 (1998), 3140. doi: 10.1109/18.737544.

[8]

T. Etzion and A. Vardy, Error-correcting codes in projective space,, IEEE Trans. Inform. Theory, 57 (2011), 1165. 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. 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. 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. 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. 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. doi: 10.1002/jcd.3180030108.

[15]

J. Schönheim, On coverings,, Pacific J. Math., 14 (1964), 1405.

[16]

M. Schwartz and T. Etzion, Codes and anticodes in the Grassman graph,, J. Combin. Theory Ser. A, 97 (2002), 27. doi: 10.1006/jcta.2001.3188.

[17]

H. Suzuki, $2$-designs over GF$(2^m)$,, Graphs Combin., 6 (1990), 293. doi: 10.1007/BF01787580.

[18]

H. Suzuki, $2$-designs over GF$(q)$,, Graphs Combin., 8 (1992), 381. doi: 10.1007/BF02351594.

[19]

S. Thomas, Designs over finite fields,, Geom. Dedicata, 21 (1987), 237.

[20]

S. Thomas, Designs and partial geometries over finite fields,, Geom. Ded., 63 (1996), 247. doi: 10.1007/BF00181415.

show all references

References:
[1]

R. Ahlswede, H. K. Aydinian and L. H. Khachatrian, On perfect codes and related concepts,, Des. Codes Crypt., 22 (2001), 221. 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. doi: 10.1007/s10623-003-4194-z.

[3]

T. Bu, Partitions of a vector space,, Disc. Math., 31 (1980), 79. 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.

[5]

D. de Caen, The current status of Turán's problem on hypergraphs,, in, (1991), 187.

[6]

C. J. Colbourn and R. Mathon, Steiner systems,, in, (2007), 102.

[7]

T. Etzion, Perfect byte-correcting codes,, IEEE Trans. Inform. Theory, 44 (1998), 3140. doi: 10.1109/18.737544.

[8]

T. Etzion and A. Vardy, Error-correcting codes in projective space,, IEEE Trans. Inform. Theory, 57 (2011), 1165. 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. 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. 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. 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. 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. doi: 10.1002/jcd.3180030108.

[15]

J. Schönheim, On coverings,, Pacific J. Math., 14 (1964), 1405.

[16]

M. Schwartz and T. Etzion, Codes and anticodes in the Grassman graph,, J. Combin. Theory Ser. A, 97 (2002), 27. doi: 10.1006/jcta.2001.3188.

[17]

H. Suzuki, $2$-designs over GF$(2^m)$,, Graphs Combin., 6 (1990), 293. doi: 10.1007/BF01787580.

[18]

H. Suzuki, $2$-designs over GF$(q)$,, Graphs Combin., 8 (1992), 381. doi: 10.1007/BF02351594.

[19]

S. Thomas, Designs over finite fields,, Geom. Dedicata, 21 (1987), 237.

[20]

S. Thomas, Designs and partial geometries over finite fields,, Geom. Ded., 63 (1996), 247. doi: 10.1007/BF00181415.

[1]

Michael Kiermaier, Reinhard Laue. Derived and residual subspace designs. Advances in Mathematics of Communications, 2015, 9 (1) : 105-115. doi: 10.3934/amc.2015.9.105

[2]

Ivica Martinjak, Mario-Osvin Pavčević. Symmetric designs possessing tactical decompositions. Advances in Mathematics of Communications, 2011, 5 (2) : 199-208. doi: 10.3934/amc.2011.5.199

[3]

Peter Boyvalenkov, Maya Stoyanova. New nonexistence results for spherical designs. Advances in Mathematics of Communications, 2013, 7 (3) : 279-292. doi: 10.3934/amc.2013.7.279

[4]

Jamshid Moori, Amin Saeidi. Some designs and codes invariant under the Tits group. Advances in Mathematics of Communications, 2017, 11 (1) : 77-82. doi: 10.3934/amc.2017003

[5]

Dean Crnković, Bernardo Gabriel Rodrigues, Sanja Rukavina, Loredana Simčić. Self-orthogonal codes from orbit matrices of 2-designs. Advances in Mathematics of Communications, 2013, 7 (2) : 161-174. doi: 10.3934/amc.2013.7.161

[6]

Crnković Dean, Vedrana Mikulić Crnković, Bernardo G. Rodrigues. On self-orthogonal designs and codes related to Held's simple group. Advances in Mathematics of Communications, 2018, 12 (3) : 607-628. doi: 10.3934/amc.2018036

[7]

Tran van Trung. Construction of 3-designs using $(1,\sigma)$-resolution. Advances in Mathematics of Communications, 2016, 10 (3) : 511-524. doi: 10.3934/amc.2016022

[8]

David Clark, Vladimir D. Tonchev. A new class of majority-logic decodable codes derived from polarity designs. Advances in Mathematics of Communications, 2013, 7 (2) : 175-186. doi: 10.3934/amc.2013.7.175

[9]

Guangzhou Chen, Yue Guo, Yong Zhang. Further results on the existence of super-simple pairwise balanced designs with block sizes 3 and 4. Advances in Mathematics of Communications, 2018, 12 (2) : 351-362. doi: 10.3934/amc.2018022

[10]

Stefka Bouyuklieva, Zlatko Varbanov. Some connections between self-dual codes, combinatorial designs and secret sharing schemes. Advances in Mathematics of Communications, 2011, 5 (2) : 191-198. doi: 10.3934/amc.2011.5.191

[11]

Luis Álvarez–cónsul, David Fernández. Noncommutative bi-symplectic $\mathbb{N}Q$-algebras of weight 1. Conference Publications, 2015, 2015 (special) : 19-28. doi: 10.3934/proc.2015.0019

[12]

B. Emamizadeh, F. Bahrami, M. H. Mehrabi. Steiner symmetric vortices attached to seamounts. Communications on Pure & Applied Analysis, 2004, 3 (4) : 663-674. doi: 10.3934/cpaa.2004.3.663

[13]

M. De Boeck, P. Vandendriessche. On the dual code of points and generators on the Hermitian variety $\mathcal{H}(2n+1,q^{2})$. Advances in Mathematics of Communications, 2014, 8 (3) : 281-296. doi: 10.3934/amc.2014.8.281

[14]

Frédéric Vanhove. A geometric proof of the upper bound on the size of partial spreads in $H(4n+1,$q2$)$. Advances in Mathematics of Communications, 2011, 5 (2) : 157-160. doi: 10.3934/amc.2011.5.157

[15]

Manish K. Gupta, Chinnappillai Durairajan. On the covering radius of some modular codes. Advances in Mathematics of Communications, 2014, 8 (2) : 129-137. doi: 10.3934/amc.2014.8.129

[16]

Dmitry Todorov. Generalizations of analogs of theorems of Maizel and Pliss and their application in shadowing theory. Discrete & Continuous Dynamical Systems - A, 2013, 33 (9) : 4187-4205. doi: 10.3934/dcds.2013.33.4187

[17]

J.I. Díaz, D. Gómez-Castro. Steiner symmetrization for concave semilinear elliptic and parabolic equations and the obstacle problem. Conference Publications, 2015, 2015 (special) : 379-386. doi: 10.3934/proc.2015.0379

[18]

Yury Neretin. The group of diffeomorphisms of the circle: Reproducing kernels and analogs of spherical functions. Journal of Geometric Mechanics, 2017, 9 (2) : 207-225. doi: 10.3934/jgm.2017009

[19]

Rafael Arce-Nazario, Francis N. Castro, Jose Ortiz-Ubarri. On the covering radius of some binary cyclic codes. Advances in Mathematics of Communications, 2017, 11 (2) : 329-338. doi: 10.3934/amc.2017025

[20]

Otávio J. N. T. N. dos Santos, Emerson L. Monte Carmelo. A connection between sumsets and covering codes of a module. Advances in Mathematics of Communications, 2018, 12 (3) : 595-605. doi: 10.3934/amc.2018035

2017 Impact Factor: 0.564

Metrics

  • PDF downloads (4)
  • HTML views (0)
  • Cited by (10)

Other articles
by authors

[Back to Top]