2017/01/16 by H. A. Helfgott, Harald Andrés Helfgott, Helfgott, Harald Andrés · 1 voice · 1 citation
Computer Science · Mathematics · #Finite Group Theory Research #Geometric and Algebraic Topology #math.GR #msc:05E18 #msc:20B15 #msc:20B25 #msc:68Q25 #msc:68R10 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1701.04372
Expository paper associated to Bourbaki seminar (Jan 14, 2017). 43 pages, in French. To appear in Astérisque. Fascicule no 1125 of the Bourbaki seminar (69th year, 2016-2017)
openalex publication_date 2017/01/16 · arxiv created 2017/10/12 · arxiv updated 2017/10/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Soient donnés deux graphes Γ1, Γ2 à n sommets. Sont-ils isomorphes? S'ils le sont, l'ensemble des isomorphismes de Γ1 à Γ2 peut être identifié avec 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 qui y sont liées -- en temps quasi-polynomial, c'est-à-dire en temps exp(O(log n)O(1)). 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é. English translation: Graph isomorphisms in quasipolynomial time [after Babai and Luks, Weisfeiler--Leman,...]. Let Γ1, Γ2 be two graphs with n vertices. Are they isomorphic? If any isomorphisms from Γ1 to Γ2 exist, they form a coset H π in the symmetric group on n elements. How can we find a representative π and a set of generators for H? 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 exp(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.