Bounds on the diameter of Cayley graphs of the symmetric group

John Bamberg; Nick Gill; Thomas Hayes; Harald 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 Hayes, Harald Helfgott, Ákos Seress, Pablo Spiga

Faculty of Computing, Engineering and Science

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

125 Downloads (Pure)

Abstract

In this paper we are concerned with the conjecture that, for any set of generators S of the symmetric group of degree 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
Publication status	Published - 2014

Keywords

math.GR
math.CO

Access to Document

10.1007/s10801-013-0476-3Licence: CC BY-NC-ND

pdfAccepted author manuscript, 9.77 MBLicence: CC BY-NC-ND

Cite this

@article{4ac1e6c55aca402086762f3f3fc92941,

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 of degree 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 = "math.GR, math.CO",

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

note = "17 pages, 6 tables",

year = "2014",

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

language = "English",

volume = "40",

pages = "1--22",

journal = "Journal of Algebraic Combinatorics",

issn = "1572-9192",

publisher = "Springer",

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

AU - Helfgott, Harald

AU - Seress, Ákos

AU - Spiga, Pablo

N1 - 17 pages, 6 tables

PY - 2014

Y1 - 2014

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

KW - math.CO

U2 - 10.1007/s10801-013-0476-3

DO - 10.1007/s10801-013-0476-3

M3 - Article

SN - 1572-9192

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

Fingerprint

Cite this