Bounds on Entanglement-Assisted Source-Channel Coding via the Lovasz ν 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 nu((G) over bar) <= nu((H) over bar), where nu represents the Lovasz number. We also obtain similar inequalities for the related Schrijver nu(-) and Szegedy nu(+) 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: alpha*(G) <= nu(-)(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 Lovasz number. Beigi introduced a quantity beta as an upper bound on a* and posed the question of whether beta(G) = right perpendicular nu(G)left perpendicular. We answer this in the affirmative and show that a related quantity is equal to inverted right perpendicular nu(G)inverted left perpendicular. We show that a quantity chi(vect)(G) recently introduced in the context of Tsirelson's problem is equal to inverted right perpendicular nu+((G) over bar )inverted left perpendicular. In an appendix, we investigate multiplicativity properties of Schrijver's and Szegedy's numbers, as well as projective rank.