A comparison of the Delsarte and Lovász bounds

A. Schrijver

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

129 Citaten (Scopus)
11 Downloads (Pure)

Samenvatting

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.
Originele taal-2Engels
Pagina's (van-tot)425-429
Aantal pagina's5
TijdschriftIEEE Transactions on Information Theory
Volume25
Nummer van het tijdschrift4
DOI's
StatusGepubliceerd - 1979

Vingerafdruk Duik in de onderzoeksthema's van 'A comparison of the Delsarte and Lovász bounds'. Samen vormen ze een unieke vingerafdruk.

Citeer dit