Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 34 min ago
PreprintCC BY 4.0arXiv

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

  • Lorenzo Ciardo
  • Iris Hebbeker
  • Gideo Joubert
  • Jana Kreiß
  • Antoine Mottet
Open at sourcePDFDOICite

Abstract

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.

Related

  1. Quantizing Delsarte Theory
    Ryutaro Misawa
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  2. The Rate of the Delsarte Bound for Binary Codes and Spheres
    Andrew Salmon
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsGeometry & topologyarXiv
  3. Types of well-founded trees and the homomorphism order
    Jakub Smolík
    arXivPreprintCC BY 4.0Full textLogic & foundationsarXiv
  4. A Lefschetz type homomorphism for coincidence of several maps
    Pryscilla dos Santos Ferreira Silva, Weslem Liberato Silva
    arXivPreprintarXiv licenceFull textGeometry & topologyarXiv
  5. Topological and Geometric Perspectives on Homomorphism Indistinguishability
    Josse van Dobben de Bruyn, Jérémie Marquès, David E. Roberson +3
    arXivPreprintCC BY-SA 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{ciardo2026schrijverdelsarte,
  title = {{Schrijver-Delsarte rigidity in association schemes and undecidability of quantum graph homomorphism}},
  author = {Lorenzo Ciardo and Iris Hebbeker and Gideo Joubert and Jana Kreiß and Antoine Mottet},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.20678},
  eprint = {2609.20678},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.20678},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Schrijver-Delsarte rigidity in association schemes and undecidability of quantum graph homomorphism
AU  - Lorenzo Ciardo
AU  - Iris Hebbeker
AU  - Gideo Joubert
AU  - Jana Kreiß
AU  - Antoine Mottet
PY  - 2026
DA  - 2026/09/17
PB  - arXiv
DO  - 10.48550/arxiv.2609.20678
UR  - https://arxiv.org/abs/2609.20678
AB  - 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.
ER  -