SMF

Exposé Bourbaki 1125 : Isomorphismes de graphes en temps quasi-polynomial (d'après Babai et Luks, Weisfeiler-Leman...)

Exposé Bourbaki 1125 : Graph isomorphism in quasipolynomial time (after Babai and Luks, Weisfeiler-Leman...)

Harald Andrés HELFGOTT
Exposé Bourbaki 1125 : Isomorphismes de graphes en temps quasi-polynomial (d'après Babai et Luks, Weisfeiler-Leman...)
  • Consulter un extrait
  •  
                
  • Année : 2019
  • Tome : 407
  • Format : Électronique
  • Langue de l'ouvrage :
    Français
  • Class. Math. : 68Q25, 68R10, 20B25, 20B15, 05E18
  • Pages : 135-182
  • DOI : 10.24033/ast.1063

Soient donnés deux graphes $\Gamma_1$, $\Gamma_2$ à~$n$ sommets. Sont-ils isomorphes? S'ils le sont, l'ensemble des isomorphismes de~$\Gamma_1$ à $\Gamma_2$ peut être identifié avec une classe $H\cdot\pi$ du groupe symétrique sur~$n$ éléments. Comment trouver $\pi$ 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\left((\log n)^{O(1)}\right)$. 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é.

Let $\Gamma_1$, $\Gamma_2$ be two graphs with $n$ vertices. Is there a bijection from the set of vertices of $\Gamma_1$ to that of $\Gamma_2$ sending $\Gamma_1$ to $\Gamma_2$? If such bijections exist, they form a coset $H\cdot \pi$ in the symmetric group on $n$ elements. How can one 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 $O\left(\exp\left((\log n)^C\right)\right)$, where $C$ is a constant. His strategy is based in part on an algorithm due to Luks (1980/82), who solved the case of graphs of bounded degree.

Isomorphismes de graphes, isomorphismes de chaînes, configurations cohérentes, designs [sic] combinatoires
Graph isomorphisms, string isomorphisms, coherent configurations, designs

Électronique
Electronic
Prix public Public price 10.00 €
Prix membre Member price 7.00 €
Quantité
Quantity
- +