Activities This Week

The Shannon capacity of a graph $G$ is defined as $\Theta(G):=\sup_n \alpha(G^{\otimes n})^{1/n}$ where $G^{\otimes n}$ is the $n$th tensor power of $G$. Determining $\Theta(G)$ is notoriously difficult, but there are two general upper bounds: Lovasz’s theta function and Haemers’ bound. In this talk, we present a fractional version of Haemers’ bound, originally due to Blasiak, which roughly works by embedding the vertices of $G$ as large subspaces under adjacency constraints. This bound is a common strengthening of both Haemers’ bound and the fractional chromatic number of a graph. We show that this fractional version out-performs any bound on the Shannon Capacity that could be attained through Haemers’ bound and show also that this bound in multiplicative, similar to Lovasz’s theta function. (Joint work with Boris Bukh)