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

Resumo Técnico: Rigidez de Schrijver–Delsarte em Esquemas de Associação e a Indecidibilidade do Homomorfismo de Grafos Quânticos

Enunciado do Problema
O artigo aborda a complexidade computacional do problema do homomorfismo de grafos quânticos, denotado por $\text{CSP}_q(G')$. Dado um grafo alvo fixo $G'$, o problema questiona se um grafo de entrada $G$ admite um homomorfismo quântico para $G'$. Embora a versão clássica deste problema seja bem compreendida (NP-completa para alvos não bipartidos, polinomial para bipartidos), o cenário quântico é menos resolvido. Sabe-se que, para estratégias quânticas irrestritas, o problema é RE-completo (completo para recursivamente enumerável) devido ao teorema $MIP^* = RE$. No entanto, estabelecer a RE-completude para grafos alvo específicos e não uniformes requer provar a existência de "gadgets de comutatividade" — estruturas que forçam as estratégias quânticas a se comportarem de maneira clássica (não contextual) ou que permitem reduções de problemas conhecidos como difíceis.

Os autores focam em uma abordagem sistemática para classificar a complexidade de $\text{CSP}_q(G)$ para famílias específicas de grafos derivados de esquemas de associação, incluindo grafos de Kneser, grafos $q$-Kneser e complementos de grafos de Johnson, Grassmann e Hamming. O desafio central é determinar quando esses grafos admitem gadgets de comutatividade, o que, de acordo com a teoria de polimorfismos quânticos, é equivalente a provar que todos os polimorfismos quânticos do grafo são não contextuais.

Metodologia
O artigo desenvolve um método espectral para estabelecer a não contextualidade de polimorfismos quânticos. A abordagem combina três pilares teóricos:

1. Theta de Schrijver e Empacotamentos Projetivos: Os autores utilizam o parâmetro de Schrijver $\vartheta^-(G)$, um fortalecimento da função theta de Lovász, que limita superiormente o número de independência $\alpha(G)$. Eles aproveitam o resultado de Roberson de que $\vartheta^-(G)$ também limita o número de empacotamento projetivo $\alpha_p(G)$, que por sua vez limita o número de independência quântica $\alpha_q(G)$. O núcleo de seu método baseia-se no caso em que esses limites são apertados ($\alpha(G) = \alpha_p(G) = \vartheta^-(G)$).
2. Rigidez e Análise de Igualdade: Quando o limite é apertado, os autores analisam a estrutura das matrizes de "certificado" que testemunham essa igualdade. Eles provam que, se um grafo admite um tipo específico de representação "Schrijver-rígida", os projetores que definem qualquer estratégia quântica perfeita devem residir em um subespaço restrito (o núcleo do certificado). Essa restrição força identidades lineares entre os projetores.
3. Representações de Disjunção Tame e Esquemas de Associação: Para traduzir a condição espectral em um critério verificável, os autores introduzem "representações de disjunção tame" (comportadas). Estas são aplicações injetivas de vértices do grafo para conjuntos de características, tal que vértices adjacentes mapeiam para conjuntos disjuntos. Eles definem uma representação como Schrijver-rígida se o núcleo do certificado ótimo de Schrijver coincidir com o espaço de incidência da representação.
   • Crucialmente, para grafos derivados de esquemas de associação (Johnson, Grassmann, Hamming), os autores provam que a Schrijver-rigidez é equivalente à Delsarte-rigidez. A Delsarte-rigidez é uma condição formulada inteiramente dentro da estrutura de programação linear (LP) do álgebra de Bose–Mesner, tornando-a computacionalmente verificável dado a matriz de autovalores do esquema.
   • Eles demonstram ainda que, se um grafo possui uma representação Schrijver-rígida "tame", as identidades lineares derivadas das restrições espectrais forçam todos os projetores em um polimorfismo quântico a comutar (não contextualidade).

Principais Contribuições e Resultados
A principal contribuição é a prova da RE-completude para o problema do homomorfismo de grafos parametrizado por várias famílias de grafos derivados de esquemas de associação métricos clássicos.

• Teorema Principal (Teorema 1.1): Os autores provam que determinar se um grafo de entrada admite um homomorfismo quântico para qualquer um dos seguintes grafos é RE-completo:

  • Grafos de Kneser $KG(n, k)$ com $n > 2k \ge 2$.
  • Complementos de grafos de Johnson $\overline{J(n, k)}$ com $n > 2k \ge 4$.
  • Grafos $q$-Kneser $KG_q(n, k)$ com $n > 2k \ge 2$ e $q$ uma potência de primo.
  • Complementos de grafos de Grassmann $\overline{J_q(n, k)}$ com $n > 2k \ge 4$ e $q$ uma potência de primo.
  • Complementos de grafos de Hamming $\overline{H(d, q)}$ com $d \ge 2$ e $q \ge 3$.

• Resolução de Questões em Aberto: Este resultado resolve a questão de complexidade para "grafos ímpares" ($O_n = KG(2n-1, n-1)$), uma classe de grafos para a qual a existência de gadgets de comutatividade era anteriormente não resolvida. Os autores estabelecem a RE-completude para esses grafos tanto no cenário oracular quanto no não-oracular.

• Estrutura Técnica: O artigo estabelece uma ponte entre a teoria espectral de grafos (limite de Schrijver) e a teoria algébrica de esquemas de associação (limite de Delsarte de LP). Eles demonstram que, para essas estruturas simétricas, as complexas condições de SDP necessárias para a não contextualidade podem ser reduzidas à verificação de condições de LP nos autovalores do esquema.

Significância e Alegações
O artigo alega fazer progressos significativos em direção a uma "classificação quântica de Hell–Nešetřil", que visa dicotomizar os problemas de homomorfismo de grafos entre aqueles solucionáveis em tempo polinomial e aqueles que são RE-completos. Ao fornecer um critério espectral (Schrijver-rigidez) que garante a RE-completude, os autores oferecem uma ferramenta sistemática para analisar novas famílias de grafos.

No entanto, os autores são modestos quanto ao escopo de seu método. Eles declaram explicitamente que sua abordagem espectral não captura todo o panorama dos problemas RE-completos. Eles fornecem contraexemplos:

• Alguns grafos (como o grafo diamante ou o own spindle de Moser) são RE-completos, mas não admitem gadgets de comutatividade (e, portanto, falham na condição de não contextualidade).
• Outros grafos (como ciclos ímpares de comprimento $\ge 5$) admitem gadgets de comutatividade, mas falham no critério espectral porque o limite de Schrijver não é apertado neles.

Consequentemente, os autores concluem que uma classificação completa provavelmente exigirá a combinação de seus argumentos espectrais com métodos combinatórios (como bifurcações de contextualidade), em vez de depender apenas da rigidez espectral. O trabalho não propõe novos protocolos experimentais, mas sim fornece um arcabouço teórico rigoroso para compreender o poder computacional do emaranhamento em jogos de homomorfismo de grafos específicos.