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

Resumen Técnico: Rigidez de Schrijver–Delsarte en Esquemas de Asociación y la Indecidibilidad del Homomorfismo de Grafos Cuánticos

Planteamiento del Problema
El artículo aborda la complejidad computacional del problema del homomorfismo de grafos cuánticos, denotado como $\text{CSP}_q(G')$. Dado un grafo objetivo fijo $G'$, el problema consiste en determinar si un grafo de entrada $G$ admite un homomorfismo cuántico hacia $G'$. Mientras que la versión clásica de este problema está bien comprendida (NP-completa para objetivos no bipartitos, polinómica para bipartitos), el panorama cuántico está menos resuelto. Se sabe que, para estrategias cuánticas sin restricciones, el problema es RE-completo (completo para conjuntos recursivamente enumerables) debido al teorema $MIP^* = RE$. Sin embargo, establecer la RE-completitud para grafos no uniformes específicos requiere probar la existencia de "gadgets de conmutatividad": estructuras que obligan a las estrategias cuánticas a comportarse de manera clásica (no contextual) o que permiten reducciones desde problemas conocidos de alta complejidad.

Los autores se centran en un enfoque sistemático para clasificar la complejidad de $\text{CSP}_q(G)$ para familias específicas de grafos derivadas de esquemas de asociación, incluyendo grafos de Kneser, grafos $q$-Kneser y los complementos de los grafos de Johnson, Grassmann y Hamming. El desafío central es determinar cuándo estos grafos admiten gadgets de conmutatividad, lo cual, según la teoría de los polimorfismos cuánticos, es equivalente a probar que todos los polimorfismos cuánticos del grafo son no contextuales.

Metodología
El artículo desarrolla un método espectral para establecer la no contextualidad de los polimorfismos cuánticos. El enfoque combina tres pilares teóricos:

1. El $\theta$ de Schrijver y los empaquetamientos proyectivos: Los autores utilizan el parámetro de Schrijver $\vartheta^-(G)$, un fortalecimiento de la función theta de Lovász, que acota el número de independencia $\alpha(G)$. Aprovechan el resultado de Roberson de que $\vartheta^-(G)$ también acota el número de empaquetamiento proyectivo $\alpha_p(G)$, que a su vez acota el número de independencia cuántica $\alpha_q(G)$. El núcleo de su método se basa en el caso donde estas cotas son ajustadas ($\alpha(G) = \alpha_p(G) = \vartheta^-(G)$).
2. Rigidez y análisis de igualdad: Cuando la cota es ajustada, los autores analizan la estructura de las matrices de "certificado" que dan fe de esta igualdad. Demuestran que si un grafo admite un tipo específico de representación "Schrijver-rígida", los proyectores que definen cualquier estrategia cuántica perfecta deben residir en un subespacio restringido (el núcleo del certificado). Esta restricción fuerza identidades lineales entre los proyectores.
3. Representaciones de disyunción mansa y esquemas de asociación: Para traducir la condición espectral en un criterio verificable, los autores introducen "representaciones de disyunción mansa" (tame disjointness representations). Estas son mapas inyectivos de los vértices del grafo a conjuntos de características tales que los vértices adyacentes mapean a conjuntos disjuntos. Definen una representación como Schrijver-rígida si el núcleo del certificado óptimo de Schrijver coincide con el espacio de incidencia de la representación.
   • Crucialmente, para grafos derivados de esquemas de asociación (Johnson, Grassmann, Hamming), los autores demuestran que la rigidez de Schrijver es equivalente a la rigidez de Delsarte. La rigidez de Delsarte es una condición formulada enteramente dentro del marco de la programación lineal (LP) del álgebra de Bose–Mesner, lo que la hace computacionalmente verificable dado la matriz de autovalores del esquema.
   • Además, muestran que si un grafo posee una representación Schrijver-rígida y "mansa", las identidades lineales derivadas de las restricciones espectrales fuerzan a que todos los proyectores en un polimorfismo cuántico conmuten (no contextualidad).

Contribuciones Clave y Resultados
La principal contribución es la prueba de la RE-completitud del problema del homomorfismo de grafos parametrizado por varias familias de grafos derivados de esquemas de asociación métricos clásicos.

• Teorema Principal (Teorema 1.1): Los autores demuestran que determinar si un grafo de entrada admite un homomorfismo cuántico hacia cualquiera de los siguientes grafos es RE-completo:

  • Grafos de Kneser $KG(n, k)$ con $n > 2k \ge 2$.
  • Complementos de grafos de Johnson $\overline{J(n, k)}$ con $n > 2k \ge 4$.
  • Grafos $q$-Kneser $KG_q(n, k)$ con $n > 2k \ge 2$ y $q$ una potencia de un primo.
  • Complementos de grafos de Grassmann $\overline{J_q(n, k)}$ con $n > 2k \ge 4$ y $q$ una potencia de un primo.
  • Complementos de grafos de Hamming $\overline{H(d, q)}$ con $d \ge 2$ y $q \ge 3$.

• Resolución de Preguntas Abiertas: Este resultado resuelve la cuestión de la complejidad para los "grafos impares" ($O_n = KG(2n-1, n-1)$), una clase de grafos para la cual la existencia de gadgets de conmutatividad no había sido resuelta previamente. Los autores establecen la RE-completitud para estos grafos tanto en entornos oraculares como no oraculares.

• Marco Técnico: El artículo establece un puente entre la teoría espectral de grafos (la cota de Schrijver) y la teoría algebraica de los esquemas de asociación (la cota LP de Delsarte). Demuestra que, para estas estructuras simétricas, las complejas condiciones de SDP requeridas para la no contextualidad pueden reducirse a la verificación de condiciones LP sobre los autovalores del esquema.

Significado y Reivindicaciones
El artículo afirma realizar un progreso significativo hacia una "clasificación de Hell–Nešetřil cuántica", que busca dicotomizar los problemas de homomorfismo de grafos en aquellos resolubles en tiempo polinómico y aquellos que son RE-completos. Al proporcionar un criterio espectral (rigidez de Schrijver) que garantiza la RE-completitud, los autores ofrecen una herramienta sistemática para analizar nuevas familias de grafos.

Sin embargo, los autores son modestos respecto al alcance de su método. Establecen explícitamente que su enfoque espectral no captura todo el paisaje de los problemas RE-completos. Proporcionan contraejemplos:

• Algunos grafos (como el grafo diamante o el espín de Moser) son RE-completos pero no admiten gadgets de conmutatidad (y, por lo tanto, fallan la condición de no contextualidad).
• Otros grafos (como los ciclos impares de longitud $\ge 5$) admiten gadgets de conmutatividad pero fallan el criterio espectral porque la cota de Schrijver no es ajustada en ellos.

En consecuencia, los autores concluyen que una clasificación completa probablemente requerirá combinar sus argumentos espectrales con métodos combinatorios (como las bifurcaciones de contextualidad) en lugar de depender únicamente de la rigidez espectral. El trabajo no propone nuevos protocolos experimentales, sino que proporciona un marco teórico riguroso para comprender el poder computacional del entrelazamiento en juegos de homomorfismo de grafos específicos.