Skip to main content

Sperner capacity of linear and nonlinear codes for the cyclic triangle

Publication ,  Journal Article
Calderbank, AR; Graham, RL; Shepp, LA; Frank, P; Li, WCW
Published in: Proceedings of the 1993 IEEE International Symposium on Information Theory
January 1, 1993

Shannon introduced the concept of zero-error capacity of a discrete memoryless channel. The channel determines an undirected graph on the symbol alphabet, where adjacency means that symbols cannot be confused at the receiver. The zero-error or Shannon capacity is an invariant of this graph. Gargano, Koerner, and Vaccaro have recently extended the concept of Shannon capacity to directed graphs. Their generalization of Shannon capacity is called Sperner capacity. We resolve a problem posed by these authors by giving the first example (the two orientations of the triangle) of a graph where the Sperner capacity depends on the orientations of the edges. Sperner capacity seems to be achieved by nonlinear codes, whereas Shannon capacity seems to be attainable by linear codes. In particular, linear codes do not achieve Sperner capacity for the cyclic triangle. We use Fourier analysis or linear programming to obtain the best upper bounds for linear codes. The bound for unrestricted codes are obtained from rank arguments, eigenvalue interlacing inequalities and polynomial algebra. The statement of the cyclic q-gon problem is very simple: what is the maximum size Nq(n) of a subset Sn of {0, 1, ..., q - 1}n with the property that for every pair of distinct vectors x = (xi), y = (yi) member of Sn, we have xj - yj ≡ 1(mod q) for some j? For q = 3 (the cyclic triangle), we show N3(n) ≅ 2n. If however Sn is a subgroup, then we give a simple proof that |Sn| ≤ √3n.

Duke Scholars

Published In

Proceedings of the 1993 IEEE International Symposium on Information Theory

Publication Date

January 1, 1993

Start / End Page

154
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Calderbank, A. R., Graham, R. L., Shepp, L. A., Frank, P., & Li, W. C. W. (1993). Sperner capacity of linear and nonlinear codes for the cyclic triangle. Proceedings of the 1993 IEEE International Symposium on Information Theory, 154.
Calderbank, A. R., R. L. Graham, L. A. Shepp, P. Frank, and W. C. W. Li. “Sperner capacity of linear and nonlinear codes for the cyclic triangle.” Proceedings of the 1993 IEEE International Symposium on Information Theory, January 1, 1993, 154.
Calderbank AR, Graham RL, Shepp LA, Frank P, Li WCW. Sperner capacity of linear and nonlinear codes for the cyclic triangle. Proceedings of the 1993 IEEE International Symposium on Information Theory. 1993 Jan 1;154.
Calderbank, A. R., et al. “Sperner capacity of linear and nonlinear codes for the cyclic triangle.” Proceedings of the 1993 IEEE International Symposium on Information Theory, Jan. 1993, p. 154.
Calderbank AR, Graham RL, Shepp LA, Frank P, Li WCW. Sperner capacity of linear and nonlinear codes for the cyclic triangle. Proceedings of the 1993 IEEE International Symposium on Information Theory. 1993 Jan 1;154.

Published In

Proceedings of the 1993 IEEE International Symposium on Information Theory

Publication Date

January 1, 1993

Start / End Page

154