A comparison of the Delsarte and Lovász bounds

A. Schrijver

Research output: Contribution to journalArticleAcademicpeer-review

130 Citations (Scopus)
11 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)425-429
Number of pages5
JournalIEEE Transactions on Information Theory
Volume25
Issue number4
DOIs
Publication statusPublished - 1979

Fingerprint Dive into the research topics of 'A comparison of the Delsarte and Lovász bounds'. Together they form a unique fingerprint.

Cite this