Network Error Correction, Part II: Lower Bounds

In Part I of this paper, the authors introduced the paradigm of network error correction as a generalization of classical link-by-link error correction. They also obtained the network generalizations of the Hamming bound and the Singleton bound in classical algebraic coding theory. In Part II, they prove the network generalization of the Gilbert-Varshamov bound and its enhancement. With the latter, they show that the tightness of the Singleton bound is preserved in the network setting. They also discuss the implication of the results in this paper.