NYJM Logo

New York Journal of Mathematics
Volume 25 (2019), 328-361

  

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, non-local 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 non-local 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 non-commutative 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 4-colorability theorem: all graphs G satisfy χalg(G) ≤ 4.

Acknowledgements

The first and second-named authors have been supported in part by NSF DMS-1500835. The third and fourth-named 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