 

J. William Helton,
Kyle P. Meyer,
V. I. Paulsen, and
Matthew Satriano
Algebras, synchronous games, and chromatic numbers of graphs
view print


Published: 
March 26, 2019. 
Keywords: 
quantum chromatic number, nonlocal game, Connes' embedding problem. 
Subject: 
Primary 46L60; Secondary 47L90, 05C25, 94C15. 


Abstract
We associate to each synchronous game a *algebra
whose representations determine whether the game has a perfect deterministic strategy, perfect quantum strategy or one of several other types of strategies studied in the theory of nonlocal games. Applying these results to the graph coloring game allows us to develop a correspondence between various chromatic numbers of a graph and the question of whether ideals in a free algebra are proper; this latter question can then be approached via noncommutative Gröbner basis methods. Furthermore, we introduce several new chromatic numbers guided by the algebra. One of these new chromatic numbers, χ_{alg}, is called the algebraic chromatic number, and one of our main results is the algebraic 4colorability theorem: all graphs G satisfy χ_{alg}(G) ≤ 4. 

Acknowledgements
The first and secondnamed authors have been supported in part by NSF DMS1500835. The third and fourthnamed authors are supported in part by NSERC Discovery Grants


Author information
J. William Helton:
Department of Mathematics
University of California at San Diega
La Jolla, CA 92093, USA
helton@ucsd.edu
Kyle P. Meyer:
Department of Mathematics
University of California at San Diega
La Jolla, CA 92093, USA
kpmeyer@ucsd.edu
Vern I. Paulsen:
Department of Pure Mathematics
University of Waterloo
Waterloo, Ontario N2L 3G1, Canada
vpaulsen@uwaterloo.ca
Matthew Satriano:
Department of Pure Mathematics
University of Waterloo
Waterloo, Ontario N2L 3G1, Canada
msatrian@uwaterloo.ca

