The Sperner Capacity of Linear and Nonlinear Codes for the Cyclic Triangle
A.R. Calderbank
, P. Frankl
, R.L. Graham
, W.-C.W. Li
and L.A. Shepp
DOI: 10.1023/A:1022424630332
Abstract
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.
Pages: 31–48
Keywords: information theory; directed graph; sperner theorem; Shannon capacity
Full Text: PDF
References
1. A. Blokhuis, "On the Sperner capacity of the cyclic triangle," J. Algebraic Combin., to appear. CALDERBANK, FRANKL, GRAHAM, LI, SHEPP
2. A. E. Brouwer and A. Schrijver, "The blocking number of an afflne space," J. Combinatorial Theory (A) 24 (1978), 251-253.
3. G. Cohen, J. Korner, and G. Simonyi, "Zero-error capacities and very different sequences," in Sequences: Combinatorics, Compression, Security and Transmission, R.M. Capacelli, eds., Springer- Verlag, 1990, 144-155.
4. J.H. Conway and N.J.A. Sloane, Sphere Packings, Lattices, and Groups, Springer-Verlag, New York, 1988.
5. L. Gargano, J. Korner, and U. Vaccaro, "Capacities: from information theory to extremal set theory," J. Amer. Math. Soc., to appear.
6. L. Gargano, J. Korner, and U. Vaccaro, "Sperner capacities," Graphs and Combinatorics to appear.
7. L. Gargano, J. Korner, and U. Vaccaro, "Sperner theorems on directed graphs and qualitative independence," J. Combinatorial Theory (A) 61 (1992), 173-192.
8. W. Haemers, Eigenvalue Techniques in Design and Graph Theory, Reidel, Dordrecht, The Netherlands,
1980. Thesis T.H. Eindhoven,
1979. Math. Centr. Tract 121, Amsterdam, 1980.
9. W. Haemers, "On some problems of Lovasz concerning the Shannon capacity of a graph," IEEE Trans. Inform. Theory 25 (1979), 231-232.
10. R.A. Horn and C.R. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, 1985.
11. F.K. Hwang and W.-C. W. Li, "Two-connectivities of extended double loop networks," submitted to J. Graph Theory.
12. R.E. Jamison, "Covering finite fields with cosets of subspaces," J. Combinatorial Theory (A), 22, (1977), 253-266.
13. J. Korner, "Intersection number and capacities of graphs," submitted to J. Combinatorial Theory (B).
14. J. Korner and G. Simonyi, "A Sperner-type theorem and qualitative independence,"J. Combinatorial Theory (A) 59 (1992), 90-103.
15. L. Lovasz, "On the Shannon capacity of a graph," IEEE Trans. Inform. Theory 25 (1979), 1-7.
16. F.J. MacWilliams and N.J.A. Sloane, The Theory of Error-Correcting Codes, North Holland, Amsterdam, 1979.
17. R.J. McEliece, E.R. Rodemich, H. Rumsey, Jr., and L.R. Welch, "New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities," IEEE Trans. Inform. Theory 23 (1977), 157-165.
18. C.E. Shannon, "The zero-error capacity of a noisy channel," IRE Trans. Inform. Theory 2 (1956), 8-19.
19. E. Sperner, "Bin Satz fiber Untermengen einer endlichen Menge," Math. Z. 27 (1928), 544-548.
2. A. E. Brouwer and A. Schrijver, "The blocking number of an afflne space," J. Combinatorial Theory (A) 24 (1978), 251-253.
3. G. Cohen, J. Korner, and G. Simonyi, "Zero-error capacities and very different sequences," in Sequences: Combinatorics, Compression, Security and Transmission, R.M. Capacelli, eds., Springer- Verlag, 1990, 144-155.
4. J.H. Conway and N.J.A. Sloane, Sphere Packings, Lattices, and Groups, Springer-Verlag, New York, 1988.
5. L. Gargano, J. Korner, and U. Vaccaro, "Capacities: from information theory to extremal set theory," J. Amer. Math. Soc., to appear.
6. L. Gargano, J. Korner, and U. Vaccaro, "Sperner capacities," Graphs and Combinatorics to appear.
7. L. Gargano, J. Korner, and U. Vaccaro, "Sperner theorems on directed graphs and qualitative independence," J. Combinatorial Theory (A) 61 (1992), 173-192.
8. W. Haemers, Eigenvalue Techniques in Design and Graph Theory, Reidel, Dordrecht, The Netherlands,
1980. Thesis T.H. Eindhoven,
1979. Math. Centr. Tract 121, Amsterdam, 1980.
9. W. Haemers, "On some problems of Lovasz concerning the Shannon capacity of a graph," IEEE Trans. Inform. Theory 25 (1979), 231-232.
10. R.A. Horn and C.R. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, 1985.
11. F.K. Hwang and W.-C. W. Li, "Two-connectivities of extended double loop networks," submitted to J. Graph Theory.
12. R.E. Jamison, "Covering finite fields with cosets of subspaces," J. Combinatorial Theory (A), 22, (1977), 253-266.
13. J. Korner, "Intersection number and capacities of graphs," submitted to J. Combinatorial Theory (B).
14. J. Korner and G. Simonyi, "A Sperner-type theorem and qualitative independence,"J. Combinatorial Theory (A) 59 (1992), 90-103.
15. L. Lovasz, "On the Shannon capacity of a graph," IEEE Trans. Inform. Theory 25 (1979), 1-7.
16. F.J. MacWilliams and N.J.A. Sloane, The Theory of Error-Correcting Codes, North Holland, Amsterdam, 1979.
17. R.J. McEliece, E.R. Rodemich, H. Rumsey, Jr., and L.R. Welch, "New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities," IEEE Trans. Inform. Theory 23 (1977), 157-165.
18. C.E. Shannon, "The zero-error capacity of a noisy channel," IRE Trans. Inform. Theory 2 (1956), 8-19.
19. E. Sperner, "Bin Satz fiber Untermengen einer endlichen Menge," Math. Z. 27 (1928), 544-548.
© 1992–2009 Journal of Algebraic Combinatorics
©
2012 FIZ Karlsruhe /
Zentralblatt MATH for the EMIS Electronic Edition