{"id":"arxiv/2609.20678","url":"https://arxiv.org/abs/2609.20678","tags":["math.CO","cs.CC","cs.DM","math.OA","quant-ph"],"score":0,"title":"Schrijver-Delsarte rigidity in association schemes and undecidability of quantum graph homomorphism","domain":"math.CO","source":"arxiv","authors":["Lorenzo Ciardo","Iris Hebbeker","Gideo Joubert","Jana Kreiß","Antoine Mottet"],"reviews":0,"subject":"math.CO","summary":"We prove RE-completeness of the quantum homomorphism problem parameterised by families of graphs derived from the classic metric association schemes. These include Kneser graphs, $q$-Kneser graphs, and the complements of Johnson, Grassmann, and Hamming graphs. Our proof develops a spectral method for establishing non-contextuality of quantum polymorphisms. It combines an equality analysis of Roberson's bound on the projective packing number in terms of Schrijver's theta with a structural argument inspired by Erdős-Ko-Rado theory.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-17","reactions":{}}