Sandwich theorems and capacity bounds for non-commutative graphs

Abstract

We define non-commutative versions of the vertex packing polytope, the theta convex body and the fractional vertex packing polytope of a graph, and establish a quantum version of the Sandwich Theorem of Grötschel, Lovász and Schrijver. We define new non-commutative versions of the Lovász number of a graph which lead to an upper bound of the zero-error capacity of the corresponding quantum channel that can be genuinely better than the one established previously by Duan, Severini and Winter. We define non-commutative counterparts of widely used classical graph parameters and establish their interrelation.

References in corpus (7)

• Zero-error communication via quantum channels, non-commutative graphs and a quantum Lovasz theta function
• Quantum source-channel coding and non-commutative graph theory
• Complexity and capacity bounds for quantum channels
• A Continuity Theorem for Stinespring's Dilation
• Chromatic numbers and a Lovász type inequality for non-commutative graphs
• Quantum asymptotic spectra of graphs and non-commutative graphs, and quantum Shannon capacities
• The Haemers bound of noncommutative graphs

Cited by in corpus (6)

• Observations on Graph Invariants with the Lovász $\vartheta$-Function
• Quantum graphs: different perspectives, homomorphisms and quantum automorphisms
• Quantum no-signalling correlations and non-local games
• The Haemers bound of noncommutative graphs
• Information theoretic parameters of non-commutative graphs and convex corners
• Weighted theta functions for non-commutative graphs