On the Diameter of Random Cayley Graphs of the Symmetric Group
- 12 September 1992
- journal article
- research article
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 1 (3) , 201-208
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).Keywords
This publication has 6 references indexed in Scilit:
- The probability of generating the symmetric groupJournal of Combinatorial Theory, Series A, 1989
- On the diameter of cayley graphs of the symmetric groupJournal of Combinatorial Theory, Series A, 1988
- The Probability that some Power of a Permutation has Small DegreeBulletin of the London Mathematical Society, 1980
- The probability of generating the symmetric groupMathematische Zeitschrift, 1969
- On some problems of a statistical group-theory. IIActa Mathematica Hungarica, 1967
- On some problems of a statistical group-theory. IProbability Theory and Related Fields, 1965