00:00:00 / 00:00:00

[1125] Isomorphismes de graphes en temps quasi-polynomial

De Harald Helfgott

Apparaît dans la 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]

Informations sur la vidéo

Bibliographie

Séminaire Bourbaki, 69ème année (2016-2017), n°1125, janvier 2017 PDF

Dernières questions liées sur MathOverflow

Pour poser une question, votre compte Carmin.tv doit être connecté à mathoverflow

Poser une question sur MathOverflow




Inscrivez-vous

  • Mettez des vidéos en favori
  • Ajoutez des vidéos à regarder plus tard &
    conservez votre historique de consultation
  • Commentez avec la communauté
    scientifique
  • Recevez des notifications de mise à jour
    de vos sujets favoris
Donner son avis