Le diamètre des associaèdres : la solution d'un problème posé il y a 25 ans - Efrei

Ce module a été développé afin de rendre le site Efrei accessible au plus grand nombre.

Si malgré notre vigilance, vous rencontriez le moindre problème d’accessibilité sur notre site, n’hésitez pas à nous contacter à l’adresse site-groupe@efrei.fr ou par téléphone au +33 188 289 000.

11 Fév 2013
Les Talents d'Efrei
  • Partager sur Twitter
  • Partager sur Facebook
  • Partager sur Linkedin
  • Partager sur Google+

Lionel Pournin, enseignant-chercheur à l’Efrei et membre du GIS AllianSTIC, a récemment résolu un problème posé, il y a 25 ans, par Daniel Sleator, Robert Tarjan et William Thurston – médaillé Fields en 1982 – au sujet du diamètre des associaèdres.

Ce résultat a déjà donné lieu à plusieurs présentations dans des séminaires universitaires : Université Paris Diderot, Université Pierre et Marie Curie, Ecole Normale Supérieure de Paris.


Les associaèdres sont des polytopes qui ont été découverts indépendamment dans plusieurs domaines des mathématiques. Le complexe de bord de l’associaèdre de dimension d peut être représenté en utilisant indifféremment les parenthésages des mots de d+2 lettres, les triangulations des polygones convexes de d+3 sommets ou encore les arbres binaires de taille d+1.

En 1988, Daniel Sleator, Robert Tarjan et William Thurston montrent que le diamètre des associaèdres n’est jamais plus grand que 2d-4 quand d est supérieur à 9. Ils montrent également que cette borne supérieure est atteinte quand d est suffisamment grand. Ils conjecturent alors que, dans cette phrase, « suffisamment grand » signifie « supérieur à 9 ».

Cette conjecture a été résolue en 2012 par Lionel Pournin. La preuve a été prépubliée sur arXiv : The diameters of associahedra.

Site personnel de Lionel Pournin (en anglais)