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

Résumé technique : Rigidité de Schrijver–Delsarte dans les schémas d'association et indécidabilité du morphisme de graphe quantique

Énoncé du problème
Le papier traite de la complexité computationnelle du problème du morphisme de graphe quantique, noté $\text{CSP}_q(G')$. Étant donné un graphe cible fixé $G'$, le problème consiste à déterminer si un graphe d'entrée $G$ admet un morphisme quantique vers $G'$. Alors que la version classique de ce problème est bien comprise (NP-complète pour les cibles non bipartites, polynomiale pour les cibles bipartites), le paysage quantique est moins résolu. Il est connu que pour des stratégies quantiques non restreintes, le problème est RE-complet (complet pour les ensembles récursivement énumérables) en raison du théorème $MIP^* = RE$. Cependant, établir la RE-complétude pour des graphes cibles spécifiques et non uniformes nécessite de prouver l'existence de « gadgets de commutativité » — des structures qui forcent les stratégies quantiques à se comporter de manière classique (non-contextuelle) ou permettent des réductions à partir de problèmes connus pour être difficiles.

Les auteurs se concentrent sur une approche systématique pour classifier la complexité de $\text{CSP}_q(G)$ pour des familles spécifiques de graphes dérivés de schémas d'association, incluant les graphes de Kneser, les graphes $q$-Kneser, et les compléments des graphes de Johnson, de Grassmann et de Hamming. Le défi central est de déterminer quand ces graphes admettent des gadgets de commutativité, ce qui, selon la théorie des polymorphismes quantiques, équivaut à prouver que tous les polymorphismes quantiques du graphe sont non-contextuels.

Méthodologie
Le papier développe une méthode spectrale pour établir la non-contextualité des polymorphismes quantiques. L'approche combine trois piliers théoriques :

1. Le Thêta de Schrijver et les packings projectifs : Les auteurs utilisent le paramètre de Schrijver $\vartheta^-(G)$, un renforcement de la fonction thêta de Lovász, qui borne le nombre d'indépendance $\alpha(G)$. Ils exploitent le résultat de Roberson selon lequel $\vartheta^-(G)$ borne également le nombre de packing projectif $\alpha_p(G)$, qui à son tour borne le nombre d'indépendance quantique $\alpha_q(G)$. Le cœur de leur méthode repose sur le cas où ces bornes sont serrées ($\alpha(G) = \alpha_p(G) = \vartheta^-(G)$).
2. Rigidité et analyse d'égalité : Lorsque la borne est serrée, les auteurs analysent la structure des matrices de « certificat » témoignant de cette égalité. Ils prouvent que si un graphe admet un type spécifique de représentation « Schrijver-rigide », les projecteurs définissant toute stratégie quantique parfaite doivent résider dans un sous-espace restreint (le noyau du certificat). Cette restriction impose des identités linéaires parmi les projecteurs.
3. Représentations de disjointure tempérées et schémas d'association : Pour traduire la condition spectrale en un critère vérifiable, les auteurs introduisent des « représentations de disjointure tempérées ». Ce sont des injections de sommets de graphes vers des ensembles de caractéristiques telles que les sommets adjacents sont injectés dans des ensembles disjoints. Ils définissent une représentation comme étant Schrijver-rigide si le noyau du certificat optimal de Schrijver coïncide avec l'espace d'incidence de la représentation.
   • Crucialement, pour les graphes dérivés de schémas d'association (Johnson, Grassmann, Hamming), les auteurs prouvent que la rigidité de Schrijver est équivalente à la rigidité de Delsarte. La rigidité de Delsarte est une condition formulée entièrement dans le cadre de la programmation linéaire (LP) de l'algèbre de Bose–Mesner, ce qui la rend vérifiable par calcul donné la matrice propre du schéma.
   • Ils démontrent en outre que si un graphe possède une représentation de Schrijver-rigide « tempérée », les identités linéaires dérivées des contraintes spectrales forcent tous les projecteurs d'un polymorphisme quantique à commuter (non-contextualité).

Contributions principales et résultats
La principale contribution est la preuve de la RE-complétude du problème de morphisme de graphe paramétré par plusieurs familles de graphes dérivées de schémas d'association métriques classiques.

• Théorème principal (Théorème 1.1) : Les auteurs prouvent que déterminer si un graphe d'entrée admet un morphisme quantique vers l'un des graphes suivants est RE-complet :

  • Graphes de Kneser $KG(n, k)$ avec $n > 2k \ge 2$.
  • Compléments des graphes de Johnson $\overline{J(n, k)}$ avec $n > 2k \ge 4$.
  • Graphes $q$-Kneser $KG_q(n, k)$ avec $n > 2k \ge 2$ et $q$ une puissance de nombre premier.
  • Compléments des graphes de Grassmann $\overline{J_q(n, k)}$ avec $n > 2k \ge 4$ et $q$ une puissance de nombre premier.
  • Compléments des graphes de Hamming $\overline{H(d, q)}$ avec $d \ge 2$ et $q \ge 3$.

• Résolution de questions ouvertes : Ce résultat tranche la question de la complexité pour les « graphes impairs » ($O_n = KG(2n-1, n-1)$), une classe de graphes pour laquelle l'existence de gadgets de commutativité était auparavant non résolue. Les auteurs établissent la RE-complétude pour ces graphes tant dans le cadre oraculaire que non-oraculaire.

• Cadre technique : Le papier établit un pont entre la théorie spectrale des graphes (borne de Schrijver) et la théorie algébrique des schémas d'association (borne LP de Delsarte). Ils démontrent que pour ces structures symétriques, les conditions complexes de SDP requises pour la non-contextualité peuvent être réduites à la vérification de conditions LP sur les valeurs propres du schéma.

Signification et affirmations
Le papier affirme faire des progrès significatifs vers une « classification de Hell–Nešetřil quantique », qui vise à dichotomiser les problèmes de morphisme de graphe en ceux solubles en temps polynomial et ceux qui sont RE-complets. En fournissant un critère spectral (rigidité de Schrijver) qui garantit la RE-complétude, les auteurs offrent un outil systématique pour analyser de nouvelles familles de graphes.

Cependant, les auteurs restent modestes quant à la portée de leur méthode. Ils déclarent explicitement que leur approche spectrale ne capture pas l'intégralité du paysage des problèmes RE-complets. Ils fournissent des contre-exemples :

• Certains graphes (comme le graphe diamant ou l'aiguille de Moser) sont RE-complets mais n'admettent pas de gadgets de commutativité (et échouent donc à la condition de non-contextualité).
• D'autres graphes (comme les cycles impairs de longueur $\ge 5$) admettent des gadgets de commutativité mais échouent au critère spectral car la borne de Schrijver n'y est pas serrée.

Par conséquent, les auteurs concluent qu'une classification complète nécessitera probablement de combiner leurs arguments spectraux avec des méthodes combinatoires (telles que les bifurcations de contextualité) plutôt que de s'appuyer uniquement sur la rigidité spectrale. Le travail ne propose pas de nouveaux protocoles expérimentaux, mais fournit plutôt un cadre théorique rigoureux pour comprendre la puissance computationnelle de l'intrication dans des jeux de morphisme de graphe spécifiques.