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]

Des. Codes Crypt., 22 (2001), 221-237. doi: 10.1023/A:1008394205999.  Google Scholar

[2]

Des. Codes Crypt., 34 (2005), 55-70. doi: 10.1007/s10623-003-4194-z.  Google Scholar

[3]

Disc. Math., 31 (1980), 79-83. doi: 10.1016/0012-365X(80)90174-0.  Google Scholar

[4]

Ars Combinatoria, 16 (1983), 5-10.  Google Scholar

[5]

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

[6]

in "Handbook of Combinatorial Designs'' (eds. C.J. Colbourn and J.H. Dinitz), CRC Press, Boca Raton, FL, (2007), 102-110.  Google Scholar

[7]

IEEE Trans. Inform. Theory, 44 (1998), 3140-3146. doi: 10.1109/18.737544.  Google Scholar

[8]

IEEE Trans. Inform. Theory, 57 (2011), 1165-1173. doi: 10.1109/TIT.2010.2095232.  Google Scholar

[9]

IEEE Trans. Comput., 21 (1972), 1322-1331. doi: 10.1109/T-C.1972.223503.  Google Scholar

[10]

Geom. Dedicata, 69 (1998), 261-286. doi: 10.1023/A:1005057610394.  Google Scholar

[11]

IEEE Trans. Inform. Theory, 54 (2008), 3579-3591. doi: 10.1109/TIT.2008.926449.  Google Scholar

[12]

Lect. Notes Comput. Sci., 5393 (2008), 31-42. doi: 10.1007/978-3-540-89994-5_4.  Google Scholar

[13]

Cambridge University Press, 1992.  Google Scholar

[14]

J. Combin. Des., 3 (1995), 61-77. doi: 10.1002/jcd.3180030108.  Google Scholar

[15]

Pacific J. Math., 14 (1964), 1405-1411.  Google Scholar

[16]

J. Combin. Theory Ser. A, 97 (2002), 27-42. doi: 10.1006/jcta.2001.3188.  Google Scholar

[17]

Graphs Combin., 6 (1990), 293-296. doi: 10.1007/BF01787580.  Google Scholar

[18]

Graphs Combin., 8 (1992), 381-389. doi: 10.1007/BF02351594.  Google Scholar

[19]

Geom. Dedicata, 21 (1987), 237-242.  Google Scholar

[20]

Geom. Ded., 63 (1996), 247-253. doi: 10.1007/BF00181415.  Google Scholar

show all references

References:
[1]

Des. Codes Crypt., 22 (2001), 221-237. doi: 10.1023/A:1008394205999.  Google Scholar

[2]

Des. Codes Crypt., 34 (2005), 55-70. doi: 10.1007/s10623-003-4194-z.  Google Scholar

[3]

Disc. Math., 31 (1980), 79-83. doi: 10.1016/0012-365X(80)90174-0.  Google Scholar

[4]

Ars Combinatoria, 16 (1983), 5-10.  Google Scholar

[5]

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

[6]

in "Handbook of Combinatorial Designs'' (eds. C.J. Colbourn and J.H. Dinitz), CRC Press, Boca Raton, FL, (2007), 102-110.  Google Scholar

[7]

IEEE Trans. Inform. Theory, 44 (1998), 3140-3146. doi: 10.1109/18.737544.  Google Scholar

[8]

IEEE Trans. Inform. Theory, 57 (2011), 1165-1173. doi: 10.1109/TIT.2010.2095232.  Google Scholar

[9]

IEEE Trans. Comput., 21 (1972), 1322-1331. doi: 10.1109/T-C.1972.223503.  Google Scholar

[10]

Geom. Dedicata, 69 (1998), 261-286. doi: 10.1023/A:1005057610394.  Google Scholar

[11]

IEEE Trans. Inform. Theory, 54 (2008), 3579-3591. doi: 10.1109/TIT.2008.926449.  Google Scholar

[12]

Lect. Notes Comput. Sci., 5393 (2008), 31-42. doi: 10.1007/978-3-540-89994-5_4.  Google Scholar

[13]

Cambridge University Press, 1992.  Google Scholar

[14]

J. Combin. Des., 3 (1995), 61-77. doi: 10.1002/jcd.3180030108.  Google Scholar

[15]

Pacific J. Math., 14 (1964), 1405-1411.  Google Scholar

[16]

J. Combin. Theory Ser. A, 97 (2002), 27-42. doi: 10.1006/jcta.2001.3188.  Google Scholar

[17]

Graphs Combin., 6 (1990), 293-296. doi: 10.1007/BF01787580.  Google Scholar

[18]

Graphs Combin., 8 (1992), 381-389. doi: 10.1007/BF02351594.  Google Scholar

[19]

Geom. Dedicata, 21 (1987), 237-242.  Google Scholar

[20]

Geom. Ded., 63 (1996), 247-253. doi: 10.1007/BF00181415.  Google Scholar

[1]

Jennifer D. Key, Bernardo G. Rodrigues. Binary codes from $ m $-ary $ n $-cubes $ Q^m_n $. Advances in Mathematics of Communications, 2021, 15 (3) : 507-524. doi: 10.3934/amc.2020079

[2]

V. V. Zhikov, S. E. Pastukhova. Korn inequalities on thin periodic structures. Networks & Heterogeneous Media, 2009, 4 (1) : 153-175. doi: 10.3934/nhm.2009.4.153

[3]

W. Cary Huffman. On the theory of $\mathbb{F}_q$-linear $\mathbb{F}_{q^t}$-codes. Advances in Mathematics of Communications, 2013, 7 (3) : 349-378. doi: 10.3934/amc.2013.7.349

[4]

Matthias Erbar, Jan Maas. Gradient flow structures for discrete porous medium equations. Discrete & Continuous Dynamical Systems, 2014, 34 (4) : 1355-1374. doi: 10.3934/dcds.2014.34.1355

[5]

Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Linear nonbinary covering codes and saturating sets in projective spaces. Advances in Mathematics of Communications, 2011, 5 (1) : 119-147. doi: 10.3934/amc.2011.5.119

[6]

János Kollár. Relative mmp without $ \mathbb{Q} $-factoriality. Electronic Research Archive, , () : -. doi: 10.3934/era.2021033

[7]

Yun Gao, Shilin Yang, Fang-Wei Fu. Some optimal cyclic $ \mathbb{F}_q $-linear $ \mathbb{F}_{q^t} $-codes. Advances in Mathematics of Communications, 2021, 15 (3) : 387-396. doi: 10.3934/amc.2020072

[8]

Fang Li, Jie Pan. On inner Poisson structures of a quantum cluster algebra without coefficients. Electronic Research Archive, , () : -. doi: 10.3934/era.2021021

[9]

Philippe Jouan, Ronald Manríquez. Solvable approximations of 3-dimensional almost-Riemannian structures. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021023

[10]

Ka Luen Cheung, Man Chun Leung. Asymptotic behavior of positive solutions of the equation $ \Delta u + K u^{\frac{n+2}{n-2}} = 0$ in $IR^n$ and positive scalar curvature. Conference Publications, 2001, 2001 (Special) : 109-120. doi: 10.3934/proc.2001.2001.109

[11]

Pengyan Ding, Zhijian Yang. Well-posedness and attractor for a strongly damped wave equation with supercritical nonlinearity on $ \mathbb{R}^{N} $. Communications on Pure & Applied Analysis, 2021, 20 (3) : 1059-1076. doi: 10.3934/cpaa.2021006

[12]

Michiyuki Watanabe. Inverse $N$-body scattering with the time-dependent hartree-fock approximation. Inverse Problems & Imaging, 2021, 15 (3) : 499-517. doi: 10.3934/ipi.2021002

[13]

Xuemin Deng, Yuelong Xiao, Aibin Zang. Global well-posedness of the $ n $-dimensional hyper-dissipative Boussinesq system without thermal diffusivity. Communications on Pure & Applied Analysis, 2021, 20 (3) : 1229-1240. doi: 10.3934/cpaa.2021018

[14]

Lei Liu, Li Wu. Multiplicity of closed characteristics on $ P $-symmetric compact convex hypersurfaces in $ \mathbb{R}^{2n} $. Discrete & Continuous Dynamical Systems, 2021, 41 (6) : 2635-3652. doi: 10.3934/dcds.2020378

[15]

Jinye Shen, Xian-Ming Gu. Two finite difference methods based on an H2N2 interpolation for two-dimensional time fractional mixed diffusion and diffusion-wave equations. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021086

[16]

Xiaoni Chi, Zhongping Wan, Zijun Hao. A full-modified-Newton step $ O(n) $ infeasible interior-point method for the special weighted linear complementarity problem. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021082

2019 Impact Factor: 0.734

Metrics

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

Other articles
by authors

[Back to Top]