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

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

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

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

[7]

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

[8]

Jamshid Moori, Bernardo G. Rodrigues, Amin Saeidi, Seiran Zandi. Designs from maximal subgroups and conjugacy classes of Ree groups. Advances in Mathematics of Communications, 2020, 14 (4) : 603-611. doi: 10.3934/amc.2020033

[9]

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

[10]

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

[11]

Vedran Krčadinac, Renata Vlahović Kruc. Quasi-symmetric designs on $ 56 $ points. Advances in Mathematics of Communications, 2021, 15 (4) : 633-646. doi: 10.3934/amc.2020086

[12]

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

[13]

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

[14]

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

[15]

Rong Wang, Xiaoni Du, Cuiling Fan. Infinite families of 2-designs from a class of non-binary Kasami cyclic codes. Advances in Mathematics of Communications, 2021, 15 (4) : 663-676. doi: 10.3934/amc.2020088

[16]

Cunsheng Ding, Chunming Tang. Infinite families of $ 3 $-designs from o-polynomials. Advances in Mathematics of Communications, 2021, 15 (4) : 557-573. doi: 10.3934/amc.2020082

[17]

Xiaoni Du, Rong Wang, Chunming Tang, Qi Wang. Infinite families of 2-designs from two classes of binary cyclic codes with three nonzeros. Advances in Mathematics of Communications, 2022, 16 (1) : 157-168. doi: 10.3934/amc.2020106

[18]

Yan Liu, Xiwang Cao. Infinite families of 2-designs from a class of affine-invariant codes. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022011

[19]

Ziling Heng, Dexiang Li, Fenjin Liu, Weiqiong Wang. Infinite families of $ t $-designs and strongly regular graphs from punctured codes. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022043

[20]

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 and Continuous Dynamical Systems - B, 2020, 25 (3) : 1001-1013. doi: 10.3934/dcdsb.2019205

2021 Impact Factor: 1.015

Metrics

  • PDF downloads (66)
  • HTML views (0)
  • Cited by (13)

Other articles
by authors

[Back to Top]