2016/05/09 by Qifu Tyler Sun, Xiaolong Yang, Keping Long +2
Computer Science · Mathematics · #Combinatorics #Computer science #Conjecture #Cooperative Communication and Network Coding #Dimension (graph theory) #Discrete mathematics #Finite field #Linear network coding #Mathematics #Multicast #Scalar (mathematics) #Scalar multiplication #Topology (electrical circuits) #cs.IT #math.IT
paper · pdf · doi:10.1109/tcomm.2016.2613085
published as IEEE TRANSACTIONS ON COMMUNICATIONS, vol. 64, no. 12, pp. 5096-5107, 2016
arxiv created 2016/05/09 · openalex publication_date 2016/09/23 · arxiv updated 2017/12/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Vector linear network coding (LNC) is a generalization of the conventional scalar LNC, such that the data unit transmitted on every edge is an L-dimensional vector of data symbols over a base field GF(q). Vector LNC enriches the choices of coding operations at intermediate nodes, and there is a popular conjecture on the benefit of vector LNC over scalar LNC in terms of alphabet size of data units: there exist (singlesource) multicast networks that are vector linearly solvable of dimension L over GF(q) but not scalar linearly solvable over any field of size q' qL. This paper introduces a systematic way to construct such multicast networks, and subsequently establish explicit instances to affirm the positive answer of this conjecture for infinitely many alphabet sizes pL with respect to an arbitrary prime p. On the other hand, this paper also presents explicit instances with the special property that they do not have a vector linear solution of dimension L over GF(2) but have scalar linear solutions over GF(q') for someq'L, where q' can be odd or even. This discovery also unveils that over a given base field, a multicast network that has a vector linear solution of dimension L does not necessarily have a vector linear solution of dimension L' > L.