Survol

Théorie des graphes, combinatoire algébrique et physique mathématique
25 juillet -19 août 2022

Cette période sur les graphes et la combinatoire sera organisée en deux parties qui ont toutes deux des liens intimes avec l’algèbre et la physique. La première partie se concentrera sur les schémas d'association et les structures algébriques sous-jacentes et la seconde sur les graphes et les questions d'informatique quantique..

Schémas d'association et algèbre

Un schéma d'association est un objet combinatoire qui généralise à la fois un groupe fini et un graphe régulier en fonction de la distance. Dans sa thèse de 1973, Delsarte a introduit deux types de schémas d'association, dits P-polynomial et Q-polynomial. A chaque schéma d'association est attachée une algèbre semi simple appelée algèbre de Bose-Mesner. Vers 1992, Terwilliger a introduit l'algèbre sous-constituante T, qui est générée par l'algèbre de Bose-Mesner et son dual. L'algèbre T est de dimension finie et semi-simple. Si le schéma est P-polynomial et Q-polynomial, alors T est une image homomorphique de l'algèbre q-Onsager. C'est l'une des raisons pour lesquelles la théorie des représentations de l'algèbre d'Onsager est actuellement très étudiée. Dans cette théorie des représentations, les notions de paire de Leonard et de paire tridiagonale jouent un rôle clé. Une paire de Leonard consiste en deux cartes linéaires sans multiplicité sur un espace vectoriel de dimension finie, qui agissent chacune sur les espaces propres de l'autre de manière tridiagonale. Une paire tridiagonale est une généralisation douce d'une paire de Leonard.

Un sujet connexe impliquant des schémas d'association a trait aux modèles de spin. Ces modèles mécaniques statistiques ont été introduits en 1989 par Vaughan Jones et utilisés pour construire des invariants pour les nœuds et les liens. Les premières avancées notables dans ce domaine sont dues à Bannai, Jaeger et Nomura. Des travaux plus récents impliquant les paires de Jones sont dus à Chan, Godsil et Munemasa. Récemment, Caughman, Curtin, Nomura, Terwilliger et Wolff ont utilisé l'algèbre des sous-constituants pour étudier les schémas d'association dont l'algèbre de Bose-Mesner contient un modèle de spin. Un problème ouvert intéressant est de trouver tous les modèles de spin qui sont contenus dans l'algèbre de Bose-Mesner d'un schéma d'association qui est P-polynomial et Q-polynomial.

Un autre sujet impliquant les schémas d'association a trait à l'algèbre de Hecke doublement affine (DAHA). Si un schéma d'association est P-polynomial et Q-polynomial, alors chaque clique de Delsarte induit un module pour la DAHA de type (C1∨,C1) grâce aux travaux récents de Jae-ho Lee. L'étude de cette connexion est un domaine de recherche actif

Graphes et informatique quantique

Les marches quantiques peuvent être considérées comme une généralisation quantique des marches aléatoires classiques (qui sont un outil important en informatique). Les marches quantiques peuvent servir de base à des algorithmes. En particulier, l'algorithme de recherche de Grover, l'un des algorithmes les plus importants de l'informatique quantique, peut être implémenté très naturellement comme une marche quantique. Les marches quantiques peuvent également être utilisées comme sous-routines dans un ordinateur quantique. La plupart des marches quantiques qui ont été proposées sont basées sur des graphes, ce qui conduit à un problème fondamental : quelle est la relation entre les propriétés de la marche et les propriétés du graphe sous-jacent ?

La théorie des homomorphismes quantiques de graphes est un développement plus récent (la thèse de doctorat de 2013 de Roberson étant l'un des principaux points de départ). Classiquement, les questions impliquant les colorations constituent une partie centrale de la théorie des graphes. Elles sont importantes en raison des problèmes théoriques qu'elles soulèvent, et parce que les algorithmes de coloration jouent un rôle significatif dans les problèmes d'ordonnancement du monde réel. Cependant, pour chaque problème classique, il existe un analogue quantique, et la relation exacte entre les deux versions n'est encore que peu comprise. Dans un certain nombre de cas, les questions relatives aux colorations et aux homomorphismes quantiques donnent lieu à des problèmes qui peuvent être résolus par des protocoles quantiques, mais qui ne sont pas solubles de manière classique. Elles fournissent donc des informations importantes sur la puissance potentielle des ordinateurs quantiques.

Les questions sur la manière de maximiser l'information obtenue à partir des mesures d'états quantiques conduisent très naturellement à des questions concernant la géométrie des ensembles de lignes dans l'espace complexe. Il est surprenant que les questions géométriques correspondantes dans l'espace réel se réduisent à des questions combinatoires qui constituent un sujet central en combinatoire algébrique, et qui sont étudiées depuis longtemps. Des questions similaires sont étudiées en analyse sous le couvert des "tight frames", mais les personnes travaillant dans ce domaine ont jusqu'à présent eu une interaction limitée avec les physiciens.