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\acute{a}sz's <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">\theta</tex> -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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">\theta \prime(G)</tex> on the independence number <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">\propto(G)</tex> of an arbitrary graph <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">G</tex> , such that <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">\theta \prime(G) \leq \theta(G)</tex> . On the other hand, if the edge set of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">G</tex> is a union of classes of a symmetric association scheme, <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">\theta(G)</tex> may be calculated by linear programming, For such graphs the product <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">\theta(G)</tex> . <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">\theta(G)</tex> is equal to the number of vertices of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">G</tex> .