#MOOC Bourbaki - 14/01/2017 - 4/4 - Harald A. HELFGOTT
Diffusé en direct le 14 janv. 2017
Isomorphismes de graphes en temps quasi-polynomial,
d’après Babai et Luks
Soient donnés deux graphes Γ1, Γ2 à n sommets. Y a-t-il une permutation des sommets qui
envoie Γ1 sur Γ2 ? Si de telles permutations existent, elles forment une classe H · π du groupe
symétrique sur n éléments. Comment trouver π et des générateurs de H?
Le défi de donner un algorithme toujours efficace en réponse à ces questions est
resté longtemps ouvert. Babai a récemment montré comment résoudre ces questions – et
d’autres questions liées – en temps quasi-polynomial, c’est-à-dire en temps O(exp((logn)
C)),
où C est une constante. Sa stratégie est basée en partie sur l’algorithme de Luks (1980/82),
qui a résolu le cas de graphes de degré borné.