Skip to main content
Erschienen in: Designs, Codes and Cryptography 2/2014

01.08.2014

Covering of subspaces by subspaces

verfasst von: Tuvi Etzion

Erschienen in: Designs, Codes and Cryptography | Ausgabe 2/2014

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Lower and upper bounds on the size of a covering of subspaces in the Grassmann graph \(\mathcal{G }_q(n,r)\) by subspaces from the Grassmann graph \(\mathcal{G }_q(n,k)\), \(k \ge r\), are discussed. The problem is of interest from four points of view: coding theory, combinatorial designs, \(q\)-analogs, and projective geometry. In particular we examine coverings based on lifted maximum rank distance codes, combined with spreads and a recursive construction. New constructions are given for \(q=2\) with \(r=2\) or \(r=3\). We discuss the density for some of these coverings. Tables for the best known coverings, for \(q=2\) and \(5 \le n \le 10\), are presented. We present some questions concerning possible constructions of new coverings of smaller size.
Literatur
1.
Zurück zum Zitat Abel R.J.R., Furino S.C.: Kirkman triple systems. In: Colburn C.J., Dinitz J.H. (eds.) The CRC Handbook of Combinatorial Designs, pp. 88–89. CRC Press, Boca Raton (1996). Abel R.J.R., Furino S.C.: Kirkman triple systems. In: Colburn C.J., Dinitz J.H. (eds.) The CRC Handbook of Combinatorial Designs, pp. 88–89. CRC Press, Boca Raton (1996).
2.
Zurück zum Zitat Ahlswede R., Aydinian H.K., Khachatrian L.H.: On perfect codes and related concepts. Des. Codes Cryptogr. 22, 221–237 (2001). Ahlswede R., Aydinian H.K., Khachatrian L.H.: On perfect codes and related concepts. Des. Codes Cryptogr. 22, 221–237 (2001).
3.
Zurück zum Zitat Beutelspacher A.: On parallelisms in finite projective spaces. Geom. Dedic. 3, 35–45 (1974). Beutelspacher A.: On parallelisms in finite projective spaces. Geom. Dedic. 3, 35–45 (1974).
4.
Zurück zum Zitat Beutelspacher A.: On \(t\)-covers in finite projective spaces. Geom. Dedic. 12, 10–16 (1979). Beutelspacher A.: On \(t\)-covers in finite projective spaces. Geom. Dedic. 12, 10–16 (1979).
5.
Zurück zum Zitat Beutelspacher A., Ueberberg J.: A characteristic property of geometric \(t\)-spreads in finite projective spaces. Eur. J. Comb. 12, 277–281 (1991). Beutelspacher A., Ueberberg J.: A characteristic property of geometric \(t\)-spreads in finite projective spaces. Eur. J. Comb. 12, 277–281 (1991).
6.
Zurück zum Zitat Blackburn S., Etzion T.: The asymptotic behavior of Grassmannian codes. IEEE Trans. Inf. Theory 58, 6605–6609 (2012). Blackburn S., Etzion T.: The asymptotic behavior of Grassmannian codes. IEEE Trans. Inf. Theory 58, 6605–6609 (2012).
7.
Zurück zum Zitat Bose R.C., Burton R.C.: A characterization of flat spaces in finite geometry and the uniqueness of the Hamming and the MacDonald codes. J. Comb. Theory 1, 96–104 (1966). Bose R.C., Burton R.C.: A characterization of flat spaces in finite geometry and the uniqueness of the Hamming and the MacDonald codes. J. Comb. Theory 1, 96–104 (1966).
8.
Zurück zum Zitat Braun M., Kerber A., Laue R.: Systematic construction of \(q\)-analogs of \(t-(v, k,\lambda )\)-designs. Des. Codes. Cryptogr. 34, 55–70 (2005). Braun M., Kerber A., Laue R.: Systematic construction of \(q\)-analogs of \(t-(v, k,\lambda )\)-designs. Des. Codes. Cryptogr. 34, 55–70 (2005).
9.
Zurück zum Zitat de Caen D.: Extension of a theorem of Moon and Moser on complete subgraphs. Ars Comb. 16, 5–10 (1983). de Caen D.: Extension of a theorem of Moon and Moser on complete subgraphs. Ars Comb. 16, 5–10 (1983).
10.
Zurück zum Zitat de Caen D.: The current status of Turán’s problem on hypergraphs. In: Frankl P., Füredi Z., Katona G., and Miklós D. (eds.) Extremal Problems for Finite Sets, pp. 187–197. János Bolyai mathematical society, Budapest (1991). de Caen D.: The current status of Turán’s problem on hypergraphs. In: Frankl P., Füredi Z., Katona G., and Miklós D. (eds.) Extremal Problems for Finite Sets, pp. 187–197. János Bolyai mathematical society, Budapest (1991).
11.
Zurück zum Zitat Delsarte P.: Bilinear forms over a finite field, with applications to coding theory. J. Comb. Theory Ser. A. 25, 226–241 (1978). Delsarte P.: Bilinear forms over a finite field, with applications to coding theory. J. Comb. Theory Ser. A. 25, 226–241 (1978).
12.
Zurück zum Zitat Eisfeld J., Metsch K.: Blocking \(s\)-dimensional subspaces by lines in PG(\(2s, q\)). Combinatorica 17, 151–162 (1997). Eisfeld J., Metsch K.: Blocking \(s\)-dimensional subspaces by lines in PG(\(2s, q\)). Combinatorica 17, 151–162 (1997).
13.
Zurück zum Zitat Etzion T., Silberstein N.: Error-correcting codes in projective space via rank-metric codes and Ferrers diagrams. IEEE Trans. Inf. Theory 55, 2909–2919 (2009). Etzion T., Silberstein N.: Error-correcting codes in projective space via rank-metric codes and Ferrers diagrams. IEEE Trans. Inf. Theory 55, 2909–2919 (2009).
14.
Zurück zum Zitat Etzion T., Silberstein N.: Codes, designs related to lifted MRD codes. IEEE Trans. Inf. Theory to appear; also in arxiv.org/abs/1102.2593 Etzion T., Silberstein N.: Codes, designs related to lifted MRD codes. IEEE Trans. Inf. Theory to appear; also in arxiv.org/abs/1102.2593
15.
Zurück zum Zitat Etzion T., Vardy A.: Error-correcting codes in projective spaces. IEEE Trans. Inf. Theory 57, 1165–1173 (2011). Etzion T., Vardy A.: Error-correcting codes in projective spaces. IEEE Trans. Inf. Theory 57, 1165–1173 (2011).
16.
Zurück zum Zitat Etzion T., Vardy A.: On \(q\)-analogs for Steiner systems and covering designs. Adv. Math. Commun. 5, 161–176 (2011). Etzion T., Vardy A.: On \(q\)-analogs for Steiner systems and covering designs. Adv. Math. Commun. 5, 161–176 (2011).
17.
Zurück zum Zitat Gabidulin E.M.: Theory of codes with maximum rank distance. Probl. Inf. Transm. 21, 1–12 (1985). Gabidulin E.M.: Theory of codes with maximum rank distance. Probl. Inf. Transm. 21, 1–12 (1985).
18.
Zurück zum Zitat Itoh T.: A new family of 2-designs over GF(\(q\)) admitting SL\(_m(q^\ell \)). Geom. Dedic. 69, 261–286 (1998). Itoh T.: A new family of 2-designs over GF(\(q\)) admitting SL\(_m(q^\ell \)). Geom. Dedic. 69, 261–286 (1998).
19.
Zurück zum Zitat Koetter R., Kschischang F.R.: Coding for errors and erasures in random network coding. IEEE Trans. Inf. Theory 54, 3579–3591 (2008). Koetter R., Kschischang F.R.: Coding for errors and erasures in random network coding. IEEE Trans. Inf. Theory 54, 3579–3591 (2008).
20.
Zurück zum Zitat Kohnert A., Kurz S.: Construction of large constant dimension codes with a prescribed minimum distance. Lect. Notes Comput. Sci. 5393, 31–42 (2008). Kohnert A., Kurz S.: Construction of large constant dimension codes with a prescribed minimum distance. Lect. Notes Comput. Sci. 5393, 31–42 (2008).
21.
Zurück zum Zitat Lunardon G.: Normal spreads. Geom. Dedic. 75, 245–261 (1999). Lunardon G.: Normal spreads. Geom. Dedic. 75, 245–261 (1999).
22.
Zurück zum Zitat Metsch K.: Blocking sets in projective spaces and polar spaces. J. Geom. 76, 216–232 (2003). Metsch K.: Blocking sets in projective spaces and polar spaces. J. Geom. 76, 216–232 (2003).
23.
Zurück zum Zitat Miyakawa M., Munemasa A., Yoshiara S.: On a class of small 2-designs over GF(\(q\)). J. Comb. Des. 3, 61–77 (1995). Miyakawa M., Munemasa A., Yoshiara S.: On a class of small 2-designs over GF(\(q\)). J. Comb. Des. 3, 61–77 (1995).
24.
Zurück zum Zitat Roth R.M.: Maximum-rank array codes and their application to crisscross error correction. IEEE Trans. Inf. Theory 37, 328–336 (1991). Roth R.M.: Maximum-rank array codes and their application to crisscross error correction. IEEE Trans. Inf. Theory 37, 328–336 (1991).
25.
Zurück zum Zitat Schönheim J.: On coverings. Pac. J. Math. 14, 1405–1411 (1964). Schönheim J.: On coverings. Pac. J. Math. 14, 1405–1411 (1964).
26.
Zurück zum Zitat Schwartz M., Etzion T.: Codes and anticodes in the Grassman graph. J. Comb. Theory Ser. A 97, 27–42 (2002). Schwartz M., Etzion T.: Codes and anticodes in the Grassman graph. J. Comb. Theory Ser. A 97, 27–42 (2002).
27.
Zurück zum Zitat Silva D., Kschischang F.R., Koetter R.: A rank-metric approach to error control in random network coding. IEEE Trans. Inf. Theory. 54, 3951–3967 (2008). Silva D., Kschischang F.R., Koetter R.: A rank-metric approach to error control in random network coding. IEEE Trans. Inf. Theory. 54, 3951–3967 (2008).
28.
Zurück zum Zitat Suzuki H.: 2-designs over GF(\(2^m\)). Gr. Comb.6, 293–296 (1990). Suzuki H.: 2-designs over GF(\(2^m\)). Gr. Comb.6, 293–296 (1990).
29.
Zurück zum Zitat Suzuki H.: 2-designs over GF(\(q\)). Gr. Comb. 8, 381–389 (1992). Suzuki H.: 2-designs over GF(\(q\)). Gr. Comb. 8, 381–389 (1992).
30.
Zurück zum Zitat Thomas S.: Designs over finite fields. Geom. Dedic. 21, 237–242 (1987). Thomas S.: Designs over finite fields. Geom. Dedic. 21, 237–242 (1987).
31.
Zurück zum Zitat Thomas S.: Designs and partial geometries over finite fields. Geom. Dedic. 63, 247–253 (1996). Thomas S.: Designs and partial geometries over finite fields. Geom. Dedic. 63, 247–253 (1996).
32.
Zurück zum Zitat van Lint J.H., Wilson R.M.: A Course in Combinatorics. Cambridge University Press, New York (1992). van Lint J.H., Wilson R.M.: A Course in Combinatorics. Cambridge University Press, New York (1992).
33.
Zurück zum Zitat Zaicev G.V., Zinoviev V.A., Semakov N.V.: Interrelations of preparata and Hamming codes and extension of Hamming codes to new double error-correcting codes. In: Proceedings of 2nd International Symposium Information Theory, pp. 257–263. Budapest (1971). Zaicev G.V., Zinoviev V.A., Semakov N.V.: Interrelations of preparata and Hamming codes and extension of Hamming codes to new double error-correcting codes. In: Proceedings of 2nd International Symposium Information Theory, pp. 257–263. Budapest (1971).
Metadaten
Titel
Covering of subspaces by subspaces
verfasst von
Tuvi Etzion
Publikationsdatum
01.08.2014
Verlag
Springer US
Erschienen in
Designs, Codes and Cryptography / Ausgabe 2/2014
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-012-9766-3

Weitere Artikel der Ausgabe 2/2014

Designs, Codes and Cryptography 2/2014 Zur Ausgabe