Bounds on entanglement assisted source-channel coding via the Lovasz theta number and its variants

We study zero-error entanglement assisted source-channel coding (communication in the presence of side information). Adapting a technique of Beigi, we show that such coding requires existence of a set of vectors satisfying orthogonality conditions related to suitably defined graphs G and H. Such vectors exist if and only if vartheta\(overline{G}\) le vartheta\(overline{H}\) where vartheta represents the Lovász number. We also obtain similar inequalities for the related Schrijver vartheta^- and Szegedy vartheta^+ numbers. These inequalities reproduce several known bounds and also lead to new results. We provide a lower bound on the entanglement assisted cost rate. We show that the entanglement assisted independence number is bounded by the Schrijver number: α^*(G) le vartheta^-(G). Therefore, we are able to disprove the conjecture that the one-shot entanglement-assisted zero-error capacity is equal to the integer part of the Lovász number. Beigi introduced a quantity β as an upper bound on α^* and posed the question of whether β(G) = lfloor vartheta(G) rfloor. We answer this in the affirmative and show that a related quantity is equal to lceil vartheta(G) rceil. We show that a quantity χ_{textrm{vect}}(G) recently introduced in the context of Tsirelson's conjecture is equal to lceil vartheta^+\(overline{G}\) rceil. In an appendix we investigate multiplicativity properties of Schrijver's and Szegedy's numbers, as well as projective rank.