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

Sintesi Tecnica: Rigidità di Schrijver–Delsarte negli Schemi di Associazione e Indecidibilità dell'Omomorfismo di Grafi Quantistici

Enunciato del Problema
Il documento affronta la complessità computazionale del problema dell'omomorfismo di grafi quantistici, denotato come $\text{CSP}_q(G')$. Dato un grafo target fisso $G'$, il problema chiede se un grafo di input $G$ ammette un omomorfismo quantistico a $G'$. Mentre la versione classica di questo problema è ben compresa (NP-completa per target non bipartiti, polinomiale per target bipartiti), il panorama quantistico è meno risolto. È noto che, per strategie quantistiche non ristrette, il problema è RE-completo (completo rispetto alla classe dei linguaggi ricorsivamente enumerabili) a causa del teorema $MIP^* = RE$. Tuttavia, stabilire la RE-completezza per specifici grafi target non uniformi richiede la prova dell'esistenza di "gadget di commutatività" — strutture che costringono le strategie quantistiche a comportarsi in modo classico (non contestuale) o che permettono riduzioni da problemi noti altrettanto difficili.

Gli autori si concentrano su un approccio sistematico per classificare la complessità di $\text{CSP}_q(G)$ per specifiche famiglie di grafi derivati da schemi di associazione, inclusi i grafi di Kneser, i grafi $q$-Kneser e i complementi dei grafi di Johnson, Grassmann e Hamming. La sfida centrale è determinare quando questi grafi ammettono gadget di commutatività, il che, secondo la teoria dei polimorfismi quantistici, equivale a dimostrare che tutti i polimorfismi quantistici del grafo sono non contestuali.

Metodologia
Il documento sviluppa un metodo spettrale per stabilire la non-contestualità dei polimorfismi quantistici. L'approccio combina tre pilastri teorici:

1. Theta di Schrijver e Packing Proiettivi: Gli autori utilizzano il parametro di Schrijver $\vartheta^-(G)$, un rafforzamento della funzione theta di Lovász, che fornisce un limite superiore per il numero di indipendenza $\alpha(G)$. Sfruttano il risultato di Roberson secondo cui $\vartheta^-(G)$ limita anche il numero di packing proiettivo $\alpha_p(G)$, il quale a sua volta limita il numero di indipendenza quantistica $\alpha_q(G)$. Il nucleo del loro metodo risiede nel caso in cui questi limiti siano stretti ($\alpha(G) = \alpha_p(G) = \vartheta^-(G)$).
2. Rigidità e Analisi dell'Uguaglianza: Quando il limite è stretto, gli autori analizzano la struttura delle matrici "certificato" che testimoniano questa uguaglianza. Dimostrano che se un grafo ammette un tipo specifico di rappresentazione "Schrijver-rigida", i proiettori che definiscono qualsiasi strategia quantistica perfetta devono risiedere in un sottospazio ristretto (il kernel del certificato). Questa restrizione impone identità lineari tra i proiettori.
3. Rappresentazioni di Disgiunzione Tame e Schemi di Associazione: Per tradurre la condizione spettrale in un criterio verificabile, gli autori introducono le "rappresentazioni di disgiunzione tame". Queste sono mappe iniettive dai vertici del grafo a insiemi di caratteristiche tali che i vertici adiacenti mappano a insiemi disgiunti. Definiscono una rappresentazione come Schrijver-rigida se il kernel del certificato ottimale di Schrijver coincide con lo spazio di incidenza della rappresentazione.
   • Crucialmente, per i grafi derivati da schemi di associazione (Johnson, Grassmann, Hamming), gli autori dimostrano che la Schrijver-rigidità è equivalente alla Delsarte-rigidità. La Delsarte-rigidità è una condizione formulata interamente all'interno del framework di programmazione lineare (LP) dell'algebra di Bose–Mesner, rendendola computazionalmente verificabile dato la matrice degli autovalori dello schema.
   • Dimostrano inoltre che se un grafo possiede una rappresentazione Schrijver-rigida "tame", le identità lineari derivate dai vincoli spettrali costringono tutti i proiettori in un polimorfismo quantistico a commutare (non-contestualità).

Contributi Principali e Risultati
Il contributo primario è la prova della RE-completezza per il problema dell'omomorfismo di grafi quantistici parametrizzato da diverse famiglie di grafi derivati da classici schemi di associazione metrici.

• Teorema Principale (Teorema 1.1): Gli autori dimostrano che determinare se un grafo di input ammette un omomorfismo quantistico a uno dei seguenti grafi è RE-completo:

  • Grafi di Kneser $KG(n, k)$ con $n > 2k \ge 2$.
  • Complementi dei grafi di Johnson $\overline{J(n, k)}$ con $n > 2k \ge 4$.
  • Grafi $q$-Kneser $KG_q(n, k)$ con $n > 2k \ge 2$ e $q$ potenza di un numero primo.
  • Complementi dei grafi di Grassmann $\overline{J_q(n, k)}$ con $n > 2k \ge 4$ e $q$ potenza di un numero primo.
  • Complementi dei grafi di Hamming $\overline{H(d, q)}$ con $d \ge 2$ e $q \ge 3$.

• Risoluzione di Questioni Aperte: Questo risultato risolve la questione della complessità per i "grafi dispari" ($O_n = KG(2n-1, n-1)$), una classe di grafi per la quale l'esistenza di gadget di commutatività era precedentemente irrisolta. Gli autori stabiliscono la RE-completezza per questi grafi sia in contesti oracolari che non oracolari.

• Framework Tecnico: Il documento stabilisce un ponte tra la teoria dei grafi spettrali (limite di Schrijver) e la teoria algebrica degli schemi di associazione (limite LP di Delsarte). Dimostra che, per queste strutture simmetriche, le complesse condizioni SDP richieste per la non-contestualità possono essere ridotte al controllo delle condizioni LP sugli autovalori dello schema.

Significato e Rivendicazioni
Il documento sostiene di compiere progressi significativi verso una "classificazione quantistica di Hell–Nešetřil", che mira a dicotomizzare i problemi di omomorfismo di grafi in quelli risolvibili in tempo polinomiale e in quelli che sono RE-completi. Fornendo un criterio spettrale (Schrijver-rigidità) che garantisce la RE-completezza, gli autori offrono uno strumento sistematico per analizzare nuove famiglie di grafi.

Tuttavia, gli autori sono modesti riguardo all'ambito del loro metodo. Essi dichiarano esplicitamente che il loro approccio spettrale non cattura l'intero panorama dei problemi RE-completi. Forniscono controesempi:

• Alcuni grafi (come il grafo a diamante o lo spindle di Moser) sono RE-completi ma non ammettono gadget di commutatività (e quindi falliscono la condizione di non-contestualità).
• Altri grafi (come i cicli dispari di lunghezza $\ge 5$) ammettono gadget di commutatività ma falliscono il criterio spettrale perché il limite di Schrijver non è stretto su di essi.

Di conseguenza, gli autori concludono che una classificazione completa richiederà probabilmente la combinazione dei loro argomenti spettrali con metodi combinatori (come le biforcazioni di contestualità) piuttosto che affidarsi solo alla rigidità spettrale. Il lavoro non propone nuovi protocolli sperimentali, ma fornisce un rigoroso framework teorico per comprendere il potere computazionale dell'entanglement in specifici giochi di omomorfismo di grafi.