published on October 10, 2024
Growth estimates and diameter bounds for linear algebraic groups
By Harald Helfgott
[1125] Isomorphismes de graphes en temps quasi-polynomial
Appears in collection : Bourbaki - Janvier 2017
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((log \ n)^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é.
[D’après Babai et Luks]
