Lovász theta type norms and operator systems

DOI10.1016/J.LAA.2015.03.022MaRDI QIDQ2341906zbMATH OpenOpenAlexFDO

Authors Carlos M. Ortiz, Vern I. Paulsen

Publication date 6 May 2015

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.7101

zbMATH Keywords

graph theoryoperator systemLovász theta function

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Operator spaces and completely bounded maps (46L07)

Abstract: To each graph on $n$ vertices there is an associated subspace of the $nimesn$ matrices called the operator system of the graph. We prove that two graphs are isomorphic if and only if their corresponding operator systems are unitally completely order isomorphic. This means that the study of graphs is equivalent to the study of these special operator systems up to the natural notion of isomorphism in their category. We define new graph theory parameters via this identification. Certain quotient norms that arise from studying the operator system of a graph give rise to a new family of parameters of a graph. We then show basic properties about these parameters and write down explicitly how to compute them via a semidefinte program, and discuss their similarities to the Lov'{a}sz theta function. Finally, we explore a particular parameter in this family and establish a sandwich theorem that holds for some graphs.

Recommendations

• Quantum chromatic numbers via operator systems
• Conic approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone
• Relaxations of graph isomorphism
• Operator systems for tolerance relations on finite sets
• The ``quantum Turán problem for operator systems

Cites work

• scientific article; zbMATH DE number 1849957 (Why is no real title available?)
• Bicliques and eigenvalues
• On the Shannon capacity of a graph
• Operator system quotients of matrix algebras and their tensor products
• Operator system structures on ordered spaces
• Quotients, exactness, and nuclearity in the operator system category
• Semidefinite Programming
• Tensor products of operator spaces
• Zero-Error Communication via Quantum Channels, Noncommutative Graphs, and a Quantum Lovász Number

Cited in

(13)

• EMBEDDINGS AND -ENVELOPES OF EXACT OPERATOR SYSTEMS
• An index for inclusions of operator systems
• Sandwich theorems and capacity bounds for non-commutative graphs
• Chromatic numbers, Sabidussi's theorem and Hedetniemi's conjecture for non-commutative graphs
• Inductive limits in the operator system and related categories
• Connections between graphs and matrix spaces
• OPERATOR SYSTEM NUCLEARITY VIA -ENVELOPES
• Random quantum graphs
• Operator systems for tolerance relations on finite sets
• Quantum chromatic number of products of quantum graphs
• A synchronous game for binary constraint systems
• Nuclearity properties and C^-envelopes of operator system inductive limits
• On coproducts of operator ᵉc-systems

This page was built for publication: Lovász theta type norms and operator systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2341906)