Bounds on the diameter of Cayley graphs of the symmetric group

Bamberg, John; Gill, Nick; Hayes, Thomas P.; Helfgott, Harald A.; Seress, Akos and Spiga, Pablo (2014). Bounds on the diameter of Cayley graphs of the symmetric group. Journal of Algebraic Combinatorics, 40(1) pp. 1–22.

DOI: https://doi.org/10.1007/s10801-013-0476-3

Abstract

In this paper we are concerned with the conjecture that, for any set of generators of the symmetric group , the word length in terms of of every permutation is bounded above by a polynomial of . We prove this conjecture for sets of generators containing a permutation fixing at least 37% of the points.

Viewing alternatives

Metrics

Item Actions

Export

You can export this page using these formats Digital Object Identifier - DOI

About

• Item ORO ID
• 38389
• Item Type
• Journal Item
• ISSN
• 1572-9192
• Keywords
• Cayley graph; diameter; Babai's conjecture; Babai-Seress conjecture.
• Academic Unit or School
• Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
  Faculty of Science, Technology, Engineering and Mathematics (STEM)
• Copyright Holders
• © 2013 Springer Science+Business Media
• Depositing User
• Nick Gill