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

Lorenzo Ciardo; Iris Hebbeker; Gideo Joubert; Jana Kreiß; Antoine Mottet

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

Lorenzo Ciardo, Iris Hebbeker, Gideo Joubert, Jana Kreiß, Antoine Mottet

arXivarxiv/2609.20678Sep 17, 2026math.COscore 0

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.

Source JSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2609.20678
curl -X POST /api/v1/records/arxiv/2609.20678/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.20678/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'