Algebras, Synchronous Games and Chromatic Numbers of Graphs

Abstract

We associate to each synchronous game an algebra whose representations determine if the game has a perfect deterministic strategy, perfect quantum strategy or one of several other perfect strategies. when applied to the graph coloring game, this leads to characterizations in terms of properties of an algebra of various quantum chromatic numbers that have been studied in the literature. This allows us to develop a correspondence between various chromatic numbers of a graph and ideals in this algebra which can then be approached via various Grobner basis methods.

arXiv comment36 pages, some proofs are machine-assisted, details of programs available on third authors webpage

References in corpus (5)

• Estimating quantum chromatic numbers
• Binary Constraint System Games and Locally Commutative Reductions
• About the Connes Embedding Conjecture---Algebraic approaches---
• Null- and Positivstellensätze for rationally resolvable ideals
• Quantum chromatic numbers via operator systems

Cited by in corpus (14)

• A synchronous game for binary constraint systems
• Bigalois extensions and the graph isomorphism game
• The quantum-to-classical graph homomorphism game
• Nonlocal Games, Compression Theorems, and the Arithmetical Hierarchy
• Synchronous linear constraint system games
• Solution group representations as quantum symmetries of graphs
• Quantum Semigroups from Synchronous Games
• Noncommutative Nullstellensätze and Perfect Games
• Products of synchronous games
• 3XOR Games with Perfect Commuting Operator Strategies Have Perfect Tensor Product Strategies and are Decidable in Polynomial Time
• Curious properties of free hypergraph C*-algebras
• Non-local games and quantum symmetries of quantum metric spaces
• Transitive Nonlocal Games
• Morphisms in categories of nonlocal games