A variant of the Lovász-Theta number based on projection matrices

Abstract

We introduce a new model for the chromatic number $\chi (G)$ based on what we call combinatorial projection matrices, which is a special class of doubly stochastic symmetric projection matrices. Relaxing this models yields an SDP whose optimal value is the projection theta number $\hat{\vartheta }(G)$, which is closely related to the Szegedy number ${\vartheta }^{+}(G)$, a variant of the Lovász theta number. We characterize that in general, $\hat{\vartheta }(G)\le {\vartheta }^{+}(G)$, with equality if $G$ is vertex-transitive. While this seems to imply that working with binary matrices is a better paradigm than working with binary eigenvalues in this context, our approach is slightly faster than computing the Szegedy number on vertex-transitive graphs.