May  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.  Google Scholar

[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.  Google Scholar

[3]

T. Bu, Partitions of a vector space,, Disc. Math., 31 (1980), 79.  doi: 10.1016/0012-365X(80)90174-0.  Google Scholar

[4]

D. de Caen, Extension of a theorem of Moon and Moser on complete subgraphs,, Ars Combinatoria, 16 (1983), 5.   Google Scholar

[5]

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

[6]

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

[7]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[13]

J. H. van Lint and R. M. Wilson, "A Course in Combinatorics,'', Cambridge University Press, (1992).   Google Scholar

[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.  Google Scholar

[15]

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

[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.  Google Scholar

[17]

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

[18]

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

[19]

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

[20]

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

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.  Google Scholar

[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.  Google Scholar

[3]

T. Bu, Partitions of a vector space,, Disc. Math., 31 (1980), 79.  doi: 10.1016/0012-365X(80)90174-0.  Google Scholar

[4]

D. de Caen, Extension of a theorem of Moon and Moser on complete subgraphs,, Ars Combinatoria, 16 (1983), 5.   Google Scholar

[5]

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

[6]

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

[7]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[13]

J. H. van Lint and R. M. Wilson, "A Course in Combinatorics,'', Cambridge University Press, (1992).   Google Scholar

[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.  Google Scholar

[15]

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

[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.  Google Scholar

[17]

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

[18]

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

[19]

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

[20]

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

[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]

Michael Braun, Michael Kiermaier, Reinhard Laue. New 2-designs over finite fields from derived and residual designs. Advances in Mathematics of Communications, 2019, 13 (1) : 165-170. doi: 10.3934/amc.2019010

[6]

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

[7]

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

[8]

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

[9]

Eun-Kyung Cho, Cunsheng Ding, Jong Yoon Hyun. A spectral characterisation of $ t $-designs and its applications. Advances in Mathematics of Communications, 2019, 13 (3) : 477-503. doi: 10.3934/amc.2019030

[10]

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

[11]

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

[12]

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

[13]

Karthikeyan Rajagopal, Serdar Cicek, Akif Akgul, Sajad Jafari, Anitha Karthikeyan. Chaotic cuttlesh: king of camouage with self-excited and hidden flows, its fractional-order form and communication designs with fractional form. Discrete & Continuous Dynamical Systems - B, 2017, 22 (11) : 0-0. doi: 10.3934/dcdsb.2019205

[14]

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

[15]

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

[16]

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

[17]

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

[18]

Shixiong Wang, Longjiang Qu, Chao Li, Huaxiong Wang. Further improvement of factoring $ N = p^r q^s$ with partial known bits. Advances in Mathematics of Communications, 2019, 13 (1) : 121-135. doi: 10.3934/amc.2019007

[19]

Huangsheng Yu, Feifei Xie, Dianhua Wu, Hengming Zhao. Further results on optimal $ (n, \{3, 4, 5\}, \Lambda_a, 1, Q) $-OOCs. Advances in Mathematics of Communications, 2019, 13 (2) : 297-312. doi: 10.3934/amc.2019020

[20]

Pak Tung Ho. Prescribing $ Q $-curvature on $ S^n $ in the presence of symmetry. Communications on Pure & Applied Analysis, 2020, 19 (2) : 715-722. doi: 10.3934/cpaa.2020033

2018 Impact Factor: 0.879

Metrics

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

Other articles
by authors

[Back to Top]