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)