Geodesic
The Sperner capacity of linear and nonlinear codes for the cyclic triangle
Journal of Algebraic Combinatorics, Tome 2 (1993) no. 1, pp. 31-48.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

Summary: 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, Körner, 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 bounds for unrestricted codes are obtained from rank arguments, eigenvalue interlacing inequalities and polynomial algebra.
Keywords: information theory, directed graph, sperner theorem, Shannon capacity 
@article{JAC_1993__2_1_a3,
     author = {Calderbank, A.R. and Frankl, P. and Graham, R.L. and Li, W.-C.W. and Shepp, L.A.},
     title = {The {Sperner} capacity of linear and nonlinear codes for the cyclic triangle},
     journal = {Journal of Algebraic Combinatorics},
     pages = {31--48},
     publisher = {mathdoc},
     volume = {2},
     number = {1},
     year = {1993},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/JAC_1993__2_1_a3/}
}
TY  - JOUR
AU  - Calderbank, A.R.
AU  - Frankl, P.
AU  - Graham, R.L.
AU  - Li, W.-C.W.
AU  - Shepp, L.A.
TI  - The Sperner capacity of linear and nonlinear codes for the cyclic triangle
JO  - Journal of Algebraic Combinatorics
PY  - 1993
SP  - 31
EP  - 48
VL  - 2
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/JAC_1993__2_1_a3/
LA  - en
ID  - JAC_1993__2_1_a3
ER  - 
%0 Journal Article
%A Calderbank, A.R.
%A Frankl, P.
%A Graham, R.L.
%A Li, W.-C.W.
%A Shepp, L.A.
%T The Sperner capacity of linear and nonlinear codes for the cyclic triangle
%J Journal of Algebraic Combinatorics
%D 1993
%P 31-48
%V 2
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/JAC_1993__2_1_a3/
%G en
%F JAC_1993__2_1_a3
Calderbank, A.R.; Frankl, P.; Graham, R.L.; Li, W.-C.W.; Shepp, L.A. The Sperner capacity of linear and nonlinear codes for the cyclic triangle. Journal of Algebraic Combinatorics, Tome 2 (1993) no. 1, pp. 31-48. http://geodesic.mathdoc.fr/item/JAC_1993__2_1_a3/