Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Designs, Codes and Cryptography
Published in: Designs, Codes and Cryptography 2/2014

01-08-2014

Covering of subspaces by subspaces

Author: Tuvi Etzion

Published in: Designs, Codes and Cryptography | Issue 2/2014

Login to get access

Activate our intelligent search to find suitable subject content or patents.

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.
previous article 2-Ranks of incidence matrices associated with conics in finite projective planes
next article New sets of frequency-hopping sequences with optimal Hamming correlation
Literature
1.
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.
Ahlswede R., Aydinian H.K., Khachatrian L.H.: On perfect codes and related concepts. Des. Codes Cryptogr. 22, 221–237 (2001).
3.
Beutelspacher A.: On parallelisms in finite projective spaces. Geom. Dedic. 3, 35–45 (1974).
4.
Beutelspacher A.: On \(t\)-covers in finite projective spaces. Geom. Dedic. 12, 10–16 (1979).
5.
Beutelspacher A., Ueberberg J.: A characteristic property of geometric \(t\)-spreads in finite projective spaces. Eur. J. Comb. 12, 277–281 (1991).
6.
Blackburn S., Etzion T.: The asymptotic behavior of Grassmannian codes. IEEE Trans. Inf. Theory 58, 6605–6609 (2012).
7.
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.
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.
de Caen D.: Extension of a theorem of Moon and Moser on complete subgraphs. Ars Comb. 16, 5–10 (1983).
10.
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.
Delsarte P.: Bilinear forms over a finite field, with applications to coding theory. J. Comb. Theory Ser. A. 25, 226–241 (1978).
12.
Eisfeld J., Metsch K.: Blocking \(s\)-dimensional subspaces by lines in PG(\(2s, q\)). Combinatorica 17, 151–162 (1997).
13.
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.
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.
Etzion T., Vardy A.: Error-correcting codes in projective spaces. IEEE Trans. Inf. Theory 57, 1165–1173 (2011).
16.
Etzion T., Vardy A.: On \(q\)-analogs for Steiner systems and covering designs. Adv. Math. Commun. 5, 161–176 (2011).
17.
Gabidulin E.M.: Theory of codes with maximum rank distance. Probl. Inf. Transm. 21, 1–12 (1985).
18.
Itoh T.: A new family of 2-designs over GF(\(q\)) admitting SL\(_m(q^\ell \)). Geom. Dedic. 69, 261–286 (1998).
19.
Koetter R., Kschischang F.R.: Coding for errors and erasures in random network coding. IEEE Trans. Inf. Theory 54, 3579–3591 (2008).
20.
Kohnert A., Kurz S.: Construction of large constant dimension codes with a prescribed minimum distance. Lect. Notes Comput. Sci. 5393, 31–42 (2008).
21.
Lunardon G.: Normal spreads. Geom. Dedic. 75, 245–261 (1999).
22.
Metsch K.: Blocking sets in projective spaces and polar spaces. J. Geom. 76, 216–232 (2003).
23.
Miyakawa M., Munemasa A., Yoshiara S.: On a class of small 2-designs over GF(\(q\)). J. Comb. Des. 3, 61–77 (1995).
24.
Roth R.M.: Maximum-rank array codes and their application to crisscross error correction. IEEE Trans. Inf. Theory 37, 328–336 (1991).
25.
Schönheim J.: On coverings. Pac. J. Math. 14, 1405–1411 (1964).
26.
Schwartz M., Etzion T.: Codes and anticodes in the Grassman graph. J. Comb. Theory Ser. A 97, 27–42 (2002).
27.
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.
Suzuki H.: 2-designs over GF(\(2^m\)). Gr. Comb.6, 293–296 (1990).
29.
Suzuki H.: 2-designs over GF(\(q\)). Gr. Comb. 8, 381–389 (1992).
30.
Thomas S.: Designs over finite fields. Geom. Dedic. 21, 237–242 (1987).
31.
Thomas S.: Designs and partial geometries over finite fields. Geom. Dedic. 63, 247–253 (1996).
32.
van Lint J.H., Wilson R.M.: A Course in Combinatorics. Cambridge University Press, New York (1992).
33.
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).
Metadata
Title
Covering of subspaces by subspaces
Author
Tuvi Etzion
Publication date
01-08-2014
Publisher
Springer US
Published in
Designs, Codes and Cryptography / Issue 2/2014
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-012-9766-3

Other articles of this Issue 2/2014

Designs, Codes and Cryptography 2/2014 Go to the issue

OriginalPaper

On the maximum size of Erdős-Ko-Rado sets in

OriginalPaper

Equations for coefficients of tactical decomposition matrices for -designs

OriginalPaper

Relative symplectic subquadrangle hemisystems of the Hermitian surface

OriginalPaper

Combinatorial solutions providing improved security for the generalized Russian cards problem

OriginalPaper

-Additive formally self-dual codes

OriginalPaper

Transitive -invariant 42-arcs in 3-dimensional projective spaces

Premium Partner

    Image Credits