Lovasz theta function bounds the Shannon capacity of graphs. What are some other uses of the function - especially in asymptotic coding theory and optimization problems?
2 Answers
$\begingroup$
$\endgroup$
2
Schrijver long ago established a connection to the Delsarte bound for a Hamming association scheme: A. Schrijver, "A comparison of the Delsarte and Lovasz bounds," IEEE Transactions on Information Theory, 25: 425-429 (1979).
-
$\begingroup$ @Joseph: Good reference. So is there a spectral characterization of minimum distance bounds in particular the GV bound? $\endgroup$– TurboCommented Nov 23, 2011 at 19:57
-
$\begingroup$ Sorry, unknown, I do not know. $\endgroup$ Commented Nov 24, 2011 at 14:37
$\begingroup$
$\endgroup$
One of the most important properties of the Lovász theta function is that for any $\epsilon >0$, it can be approximated to within an $\epsilon$ additive error in polynomial time (by the Ellipsoid Method).
Moreover, for every graph $G$, it is well-known that
$$\alpha(G) \leq \vartheta(G) \leq \overline{\chi}(G),$$
where $\alpha(G)$ is the size of a largest independent in $G$, $\vartheta(G)$ is the Lovasz theta number of $G$, and $\overline{\chi}(G)$ is the chromatic number of the complement of $G$.
For perfect graphs, we have $\alpha(G) = \vartheta(G) = \overline{\chi}(G)$. In particular $\vartheta(G)$ is always an integer. Therefore, rounding an approximation of the Lovász theta function yields a polynomial-time algorithm to compute the chromatic number of perfect graphs. As far as I know, no other efficient algorithm is known.