A counterexample to the quantum Hedetniemi conjecture

arXiv:2609.20690 · math.CO, quant-ph · Submitted 2026-09-17 · Read on arXiv

math.CO, quant-ph

Submitted: 2026-09-17

Updated: 2026-09-17

Code: https://github.com/JuliusAZeiss/Lean-Verification-and-More-Quantum-Hedetniemi-conjecture

Terminology

• Adjacency Matrix — 5× in this paper · explained in 1 episode
• Hilbert Space — 4× in this paper · explained in 2 episodes
• Trace — 4× in this paper · explained in 2 episodes
• Verification — 3× in this paper · explained in 2 episodes
• Generative AI — 2× in this paper · explained in 2 episodes
• Core — 1× in this paper · explained in 2 episodes
• Formal Verification — 1× in this paper · explained in 2 episodes
• Graph Construction — 1× in this paper · explained in 3 episodes

Sources

• On the quantum chromatic number of a graph
• Spectral lower bounds for the quantum chromatic number of a graph
• Vector Coloring the Categorical Product of Graphs
• Sabidussi Versus Hedetniemi for Three Variations of the Chromatic Number
• Algebras, Synchronous Games and Chromatic Numbers of Graphs
• A synchronous game for binary constraint systems
• Graph Homomorphisms for Quantum Players
• Quantum Graph Homomorphisms via Operator Systems
• Estimating quantum chromatic numbers
• Quantum chromatic numbers via operator systems
• Relatively small counterexamples to Hedetniemi's conjecture
• A survey on Hedetniemi's conjecture

Related papers

• Exponential random graph models with soft clique constraints
• Exact Enumeration of Phylogenetic Networks: The Tree-Child, Reticulation-Visible and Orchard Hierarchy
• Sedentary quantum walks on bipartite and planar graphs