A comparison of the Delsarte and Lovász bounds

Delsarte's linear programming bound (an upper bound on the cardinality of cliques in association schemes) is compared with Lov{a}sz'sθ-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 boundθ (G)on the independence number∝(G)of an arbitrary graphG, such thatθ (G) ≤ θ(G). On the other hand, if the edge set ofGis a union of classes of a symmetric association scheme,θ(G)may be calculated by linear programming, For such graphs the productθ(G).θ(G)is equal to the number of vertices ofG.