Affordable Access

Access to the full text

Bounds on the diameter of Cayley graphs of the symmetric group

Authors
  • Bamberg, John1
  • Gill, Nick2
  • Hayes, Thomas P.3
  • Helfgott, Harald A.4
  • Seress, Ákos1, 5
  • Spiga, Pablo6
  • 1 University of Western Australia, School of Mathematics and Statistics, 35 Stirling Highway, Crawley, WA, 6009, Australia , Crawley (Australia)
  • 2 The Open University, Department of Mathematics, Walton Hall, Milton Keynes, MK7 6AA, UK , Milton Keynes (United Kingdom)
  • 3 1 University of New Mexico, Department of Computer Science, Mail stop: MSC01 1130, Albuquerque, NM, 87131-0001, USA , Albuquerque (United States)
  • 4 École normale supérieure, Département de mathématiques et applications, 45 rue d’Ulm, Paris, 75230, France , Paris (France)
  • 5 The Ohio State University, Department of Mathematics, 231 W. 18th Avenue, Columbus, OH, 43210, USA , Columbus (United States)
  • 6 University of Milano-Bicocca, Dipartimento di Matematica e Applicazioni, Via Cozzi 53, Milano, 20125, Italy , Milano (Italy)
Type
Published Article
Journal
Journal of Algebraic Combinatorics
Publisher
Springer US
Publication Date
Oct 03, 2013
Volume
40
Issue
1
Pages
1–22
Identifiers
DOI: 10.1007/s10801-013-0476-3
Source
Springer Nature
Keywords
License
Yellow

Abstract

In this paper we are concerned with the conjecture that, for any set of generators S of the symmetric group \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\operatorname {Sym}(n)$\end{document}, the word length in terms of S of every permutation is bounded above by a polynomial of n. We prove this conjecture for sets of generators containing a permutation fixing at least 37 % of the points.

Report this publication

Statistics

Seen <100 times