Soient G un groupe fini et A un ensemble de générateurs de A. Le diamètre diam(Gamma(G,A)) du graphe de Cayley Gamma(G,A) est le l minimal tel que chaque élément de G peut être écrit comme un produit de longueur <=l d'éléments de A et A^{-1}. La question est : comment borner diam(G):= max_A diam(Gamma(G,A)) ?

Il a été conjecturé durant longtemps que le diamètre du groupe symétrique sur $n$ lettres est borné par une puissance de n, mais la meilleure borne connue était exponentielle en sqrt(n log n). Nous avons prouvé une borne quasi polynomiale :

diam(G) = exp(O(log n)^4 log log n) = exp((log log |G|)^O(1)).

Par des résultats standard, ceci implique la même borne pour tous les groupes de permutations transitifs.

Travail commun avec A. Seress.