Combinatorics, Probability and Computing

Research Article

On the Diameter of Random Cayley Graphs of the Symmetric Group

L. Babaia1 and G. L. Hetyeia2

a1 Department of Computer Science, University of Chicago, 1100 E 58th St, Chicago IL 60637–1504 and Eötvös University, Budapest, Hungary E-mail: laci@cs.uchicago.edu

a2 Department of Mathematics, M.I.T., Cambridge MA 02139 E-mail: hetyei@athena.mit.edu

Abstract

Let σ, π be two permutations selected at random from the uniform distribution on the symmetric group Sn. By a result of Dixon [5], the subgroup G generated by σ, π is almost always (i.e. with probability approaching 1 as n → ∞) either Sn or the alternating group An. We prove that the diameter of the Cayley graph of G defined by {σ, π} is almost always not greater than exp ((½ + o(l)). (In n)2).

(Received January 19 1992)

Footnotes

† Research partially supported by OTKA Grant No 2581.