Subspace packings: constructions and bounds


Creative Commons License

Etzion T., Kurz S., Otal K., ÖZBUDAK F.

DESIGNS CODES AND CRYPTOGRAPHY, vol.88, no.9, pp.1781-1810, 2020 (Journal Indexed in SCI) identifier identifier

  • Publication Type: Article / Article
  • Volume: 88 Issue: 9
  • Publication Date: 2020
  • Doi Number: 10.1007/s10623-020-00732-z
  • Title of Journal : DESIGNS CODES AND CRYPTOGRAPHY
  • Page Numbers: pp.1781-1810
  • Keywords: Subspace packings, Generalized combination networks, Vector network coding, q-analogs of designs, Grassmannian codes, Rank-metric codes, ERROR-CORRECTING CODES, T-DESIGNS, LARGE SETS, VECTOR-SPACES, Q-ANALOGS, PARALLELISMS, GEOMETRIES, 2-DESIGNS

Abstract

Grassmannian Gq (n, k) is the set of all k-dimensional subspaces of the vector space Fn q. Kotter and Kschischang showed that codes in Grassmannian space can be used for error-correction in random network coding. On the other hand, these codes are q-analogs of codes in the Johnson scheme, i.e. constant dimension codes. These codes of the Grassmannian Gq (n, k) also form a family of q-analogs of block designs and they are called subspace designs. In this paper, we examine one of the last families of q-analogs of block designs which was not considered before. This family called subspace packings is the q-analog of packings, and was considered recently for network coding solution for a family of multicast networks called the generalized combination networks. A subspace packing t-(n, k,.) q is a set S of k-subspaces from Gq (n, k) such that each t-subspace of Gq (n, t) is contained in at most. elements of S. The goal of this work is to consider the largest size of such subspace packings. We derive a sequence of lower and upper bounds on the maximum size of such packings, analyse these bounds, and identify the important problems for further research in this area.