Graph Parameters via Operator Systems

Date

2015-12

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

This work is an attempt to bridge the gap between the theory of operator systems and various aspects of graph theory.

We start by showing that two graphs are isomorphic if and only if their corresponding operator systems are isomorphic with respect to their order structure. 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 then define a new family of graph theory parameters using this identification. It turns out that these parameters share a lot in common with the Lov'{a}sz theta function, in particular we can write down explicitly how to compute them via a semidefinte program. Moreover, we explore a particular parameter in this family and establish a sandwich theorem that holds for some graphs.

Next, we move on to explore the concept of a graph homomorphism through the lens of C-algebras and operator systems. We start by studying the various notions of a quantum graph homomorphism and examine how they are related to each other. We then define and study a C-algebra that encodes all the information about these homomorphisms and establish a connection between computational complexity and the representation of these algebras. We use this C-algebra to define a new quantum chromatic number and establish some basic properties of this number. We then suggest a way of studying these quantum graph homomorphisms using certain completely positive maps and describe their structure. Finally, we use these completely positive maps to define the notion of a ``quantum" core of a graph.

Description

Keywords

Operator algebras, Graph Theory

Citation