Lovász theta type norms and operator systems

DOI10.1016/J.LAA.2015.03.022zbMATH Open1327.46053arXiv1412.7101OpenAlexW2962890363MaRDI QIDQ2341906FDOQ2341906

Carlos M. Ortiz, Vern I. Paulsen

Publication date: 6 May 2015

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

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.

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)

Cites Work

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

Cited In (11)

• EMBEDDINGS AND -ENVELOPES OF EXACT 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
• Nuclearity properties and $C^*$-envelopes of operator system inductive limits
• OPERATOR SYSTEM NUCLEARITY VIA -ENVELOPES
• Random quantum graphs
• Operator systems for tolerance relations on finite sets
• A synchronous game for binary constraint systems
• 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)