Hostname: page-component-78c5997874-xbtfd Total loading time: 0 Render date: 2024-11-05T07:00:38.577Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Diameter of Random Cayley Graphs of the Symmetric Group

Published online by Cambridge University Press:  12 September 2008

L. Babai  and
G. L. Hetyei
L. Babai
Affiliation:
Department of Computer Science, University of Chicago, 1100 E 58th St, Chicago IL 60637–1504 and Eötvös University, Budapest, Hungary E-mail: [email protected]
G. L. Hetyei
Affiliation:
Department of Mathematics, M.I.T., Cambridge MA 02139 E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

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).

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 1 , Issue 3 , September 1992 , pp. 201 - 208
Copyright
Copyright © Cambridge University Press 1992

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Babai, L. and Seress, Á. (1988) On the Diameter of the Cayley Graphs of the Symmetric Group. J. Combinatorial Theory, Ser. A 49 175–179.CrossRefGoogle Scholar
[2]Babai, L. (1989) The Probability of Generating the Symmetric Group. J. Combinatorial Theory. Ser. A 52 148–153.CrossRefGoogle Scholar
[3]Babai, L., Hetyei, G., Kantor, W. M., Lubotsky, A. and Seress, Á. (1990) On the diameter of finite groups. In: Proc. 31st IEEE Symp. on Foundations of Computer Science, St. Louis MO.857–865.Google Scholar
[4]Bovey, J. D. (1980) The probability that some power of a permutation has small degree. Bull. London Math. Soc. 12 47–51.CrossRefGoogle Scholar
[5]Dixon, J. D. (1969) The Probability of Generating the Symmetric Group. Math.Z. 110 199–205.CrossRefGoogle Scholar
[6]Erdős, P. and Turán, P. (1965) On some problems of a Statistical Group-Theory I. Wahrscheinlichkeitstheorie u. verw. Geb. 4 175–186.CrossRefGoogle Scholar
[7]Erdős, P. and Turán, P. (1967) On some problems of a Statistical Group-Theory II. Acta Math. Acad. Sci. Hung. 18 151–163.CrossRefGoogle Scholar
[8]Goncharov, V. L. (1944) On the Field of Combinatory Analysis. Isvestija Akad. Nauk. SSSR, Ser. mat. 8 3–48 (Russian. English translation: (1962) Translations of the AMS, Ser. 2,19 1–46.)Google Scholar
[9]Hardy, G. H. and Wright, E. M. (1960) An Introduction to the Theory of Numbers. Clarendon Press, Oxford.Google Scholar