Schrijver-Delsarte rigidity in association schemes and undecidability of quantum graph homomorphism

arXiv:2609.20678 · math.CO, cs.CC, cs.DM, math.OA, quant-ph · Submitted 2026-09-17 · Read on arXiv

math.CO, cs.CC, cs.DM, math.OA, quant-ph

Submitted: 2026-09-17

Updated: 2026-09-17

Terminology

• Adjacency Matrix — 12× in this paper · explained in 1 episode
• Hilbert Space — 11× in this paper · explained in 2 episodes
• Verifier — 5× in this paper · explained in 2 episodes
• Hamming Distance — 4× in this paper · explained in 2 episodes
• Core — 3× in this paper · explained in 2 episodes
• Entanglement — 2× in this paper · explained in 3 episodes
• Trace — 2× in this paper · explained in 2 episodes

Sources

• Quantum Polymorphisms and the Complexity of Quantum Constraint Satisfaction
• Existence and nonexistence of commutativity gadgets for entangled CSPs
• Binary Constraint System Games and Locally Commutative Reductions
• Spectral upper bound on the quantum k-independence number of a graph

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