Isomorphismes de graphes en temps quasi-polynomial (d’après Babai et Luks, Weisfeiler-Leman, ...)

Not valid abstract: Soient donn'es deux graphes $, $ `a $ sommets. Sont-ils isomorphes? S'ils le sont, l'ensemble des isomorphismes de $ `a $ peut ^etre identifi'e avec une classe pi$ du groupe sym'etrique sur $ 'el'ements. Comment trouver $ et des g'en'erateurs de 0 Le d'efi de donner un algorithme toujours efficace en r'eponse `a ces questions est rest'e longtemps ouvert. Babai a r'ecemment montr'e comment r'esoudre ces questions -- et d'autres qui y sont li'ees -- en temps quasi-polynomial, c'est-`a-dire en temps (O(log n)^{O(1)})$. Sa strat'egie est bas'ee en partie sur l'algorithme de Luks (1980/82), qui a r'esolu le cas de graphes de degr'e born'e. English translation: Graph isomorphisms in quasipolynomial time [after Babai and Luks, Weisfeiler--Leman,...]. Let $, $ be two graphs with $ vertices. Are they isomorphic? If any isomorphisms from $ to $ exist, they form a coset pi$ in the symmetric group on $ elements. How can we find a representative $ and a set of generators for 0 Finding an algorithm that answers such questions efficiently (in all cases) is a challenge that has long remained open. Babai has recently shown how to solve these problems and related ones in quasipolynomial time, i.e., time (O(log n)^{O(1)})$. His strategy is based in part on an algorithm due to Luks (1980/82), who solved the case of graphs of bounded degree.