A comparison of the Delsarte and Lovász bounds
- 1 July 1979
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 25 (4) , 425-429
- https://doi.org/10.1109/tit.1979.1056072
Abstract
Delsarte's linear programming bound (an upper bound on the cardinality of cliques in association schemes) is compared with Lovacute{a}sz'stheta-function bound (an upper bound on the Shannon capacity of a graph). The two bounds can be treated in a uniform fashion. Delsarte's linear programming bound can be generalized to a boundtheta prime(G)on the independence numberpropto(G)of an arbitrary graphG, such thattheta prime(G) leq theta(G). On the other hand, if the edge set ofGis a union of classes of a symmetric association scheme,theta(G)may be calculated by linear programming, For such graphs the producttheta(G).theta(G)is equal to the number of vertices ofG.Keywords
This publication has 4 references indexed in Scilit:
- On Some Problems of Lovász Concerning the Shannon Capacity of a GraphIEEE Transactions on Information Theory, 1979
- On the Shannon capacity of a graphIEEE Transactions on Information Theory, 1979
- Bounds for binary codes of length less than 25IEEE Transactions on Information Theory, 1978
- The zero error capacity of a noisy channelIEEE Transactions on Information Theory, 1956