10
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Isomorphismes de graphes en temps quasi-polynomial (d'apr\`es Babai et Luks, Weisfeiler-Leman...)

      Preprint

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          Soient donn\'es deux graphes \(\Gamma_1\), \(\Gamma_2\) \`a \(n\) sommets. Sont-ils isomorphes? S'ils le sont, l'ensemble des isomorphismes de \(\Gamma_1\) \`a \(\Gamma_2\) peut \^etre identifi\'e avec une classe \(H \pi\) du groupe sym\'etrique sur \(n\) \'el\'ements. Comment trouver \(\pi\) et des g\'en\'erateurs de \(H\)? 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 \(\exp(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 \(\Gamma_1\), \(\Gamma_2\) be two graphs with \(n\) vertices. Are they isomorphic? If any isomorphisms from \(\Gamma_1\) to \(\Gamma_2\) exist, they form a coset \(H \pi\) in the symmetric group on \(n\) elements. How can we find a representative \(\pi\) 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.

          Related collections

          Most cited references1

          • Record: found
          • Abstract: not found
          • Article: not found

          Isomorphism of graphs of bounded valence can be tested in polynomial time

            Bookmark

            Author and article information

            Journal
            2017-01-16
            Article
            1701.04372
            a86253bc-da17-4aa1-9dec-b3aa4e4f5d14

            http://arxiv.org/licenses/nonexclusive-distrib/1.0/

            History
            Custom metadata
            68Q25, 68R10, 20B25, 20B15, 05E18
            Expository paper associated to Bourbaki seminar (Jan 14, 2017). 43 pages, in French. To appear in Ast\'erisque. Fascicule no 1125 of the Bourbaki seminar (69th year, 2016-2017)
            math.GR

            Algebra
            Algebra

            Comments

            Comment on this article