Bounds on the diameter of Cayley graphs of the symmetric group

John Bamberg; Nick Gill; Thomas P. Hayes; Harald A. Helfgott; Ákos Seress; Pablo Spiga

doi:10.1007/s10801-013-0476-3

Bounds on the diameter of Cayley graphs of the symmetric group

John Bamberg
, Nick Gill
, Thomas P. Hayes
, Harald A. Helfgott
, Ákos Seress
, Pablo Spiga

Department of Computer Science and Engineering

University of Western Australia
Open University Milton Keynes
École Normale Supérieure
Ohio State University
University of Milan - Bicocca

Research output: Contribution to journal › Article › peer-review

7 Scopus citations

Abstract

In this paper we are concerned with the conjecture that, for any set of generators S of the symmetric group Sym(n), 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.

Original language	English
Pages (from-to)	1-22
Number of pages	22
Journal	Journal of Algebraic Combinatorics
Volume	40
Issue number	1
DOIs	https://doi.org/10.1007/s10801-013-0476-3
State	Published - Aug 2014

Keywords

Babai's conjecture
Babai-Seress conjecture
Cayley graph
Diameter

Access to Document

10.1007/s10801-013-0476-3

Cite this

@article{56691f975de84e52a03a454816d18b1e,

title = "Bounds on the diameter of Cayley graphs of the symmetric group",

abstract = "In this paper we are concerned with the conjecture that, for any set of generators S of the symmetric group Sym(n), 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.",

keywords = "Babai's conjecture, Babai-Seress conjecture, Cayley graph, Diameter",

author = "John Bamberg and Nick Gill and Hayes, \{Thomas P.\} and Helfgott, \{Harald A.\} and {\'A}kos Seress and Pablo Spiga",

year = "2014",

month = aug,

doi = "10.1007/s10801-013-0476-3",

language = "English",

volume = "40",

pages = "1--22",

journal = "Journal of Algebraic Combinatorics",

issn = "0925-9899",

publisher = "Springer Netherlands",

number = "1",

}

TY - JOUR

T1 - Bounds on the diameter of Cayley graphs of the symmetric group

AU - Bamberg, John

AU - Gill, Nick

AU - Hayes, Thomas P.

AU - Helfgott, Harald A.

AU - Seress, Ákos

AU - Spiga, Pablo

PY - 2014/8

Y1 - 2014/8

N2 - In this paper we are concerned with the conjecture that, for any set of generators S of the symmetric group Sym(n), 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.

AB - In this paper we are concerned with the conjecture that, for any set of generators S of the symmetric group Sym(n), 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.

KW - Babai's conjecture

KW - Babai-Seress conjecture

KW - Cayley graph

KW - Diameter

UR - https://www.scopus.com/pages/publications/84904735026

U2 - 10.1007/s10801-013-0476-3

DO - 10.1007/s10801-013-0476-3

M3 - Article

AN - SCOPUS:84904735026

SN - 0925-9899

VL - 40

SP - 1

EP - 22

JO - Journal of Algebraic Combinatorics

JF - Journal of Algebraic Combinatorics

IS - 1

ER -

Bounds on the diameter of Cayley graphs of the symmetric group

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this