The folklore polynomial diameter conjecture for transitive permutation groups

Let G≤SnG\leq S_n be a transitive permutation group. The diameter of GG is defined using the maximum over generating sets, namely diam⁡(G)=max⁡{diam⁡(G,X):X a generating set for G}\operatorname{diam}(G)=\max\{\operatorname{diam}(G,X):X\text{ a generating set for }G\}. Folklore conjecture.

diam⁡(G)≪nO(1).\operatorname{diam}(G)\ll n^{O(1)}.

This conjecture concerns polynomial diameter bounds for arbitrary transitive permutation groups. It is attributed to folklore and was made explicit in work of Kornhauser–Miller–Spirakis and McKenzie. The paper notes that it would follow conditionally from Babai’s conjecture and that no transitive permutation group is known with diameter greater than quadratic.

References

Primary source

Sean Eberhard, Elena Maini, Luca Sabatini and Gareth Tracey, “Diameter bounds for arbitrary finite groups and applications”, arXiv:2604.15303 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.