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

Cyfadran Cyfrifiadureg, Peirianneg a Gwyddoniaeth

Allbwn ymchwil: Cyfraniad at gyfnodolyn › Erthygl › adolygiad gan gymheiriaid

83 Wedi eu Llwytho i Lawr (Pure)

Crynodeb

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.

Iaith wreiddiol	Saesneg
Tudalennau (o-i)	1-22
Nifer y tudalennau	22
Cyfnodolyn	Journal of Algebraic Combinatorics
Cyfrol	40
Rhif cyhoeddi	1
Dynodwyr Gwrthrych Digidol (DOIs)	https://doi.org/10.1007/s10801-013-0476-3
Statws	Cyhoeddwyd - 2014

Mynediad at Ddogfen

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

pdfLlawysgrif awdur wedi’i dderbyn, 9.77 MBTrwydded: CC BY-NC-ND

Dyfynnu hyn

@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 = "0925-9899",

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

VL - 40

SP - 1

EP - 22

JO - Journal of Algebraic Combinatorics

JF - Journal of Algebraic Combinatorics

SN - 0925-9899

IS - 1

ER -

Bounds on the diameter of Cayley graphs of the symmetric group

Crynodeb

Mynediad at Ddogfen

Ôl bys

Dyfynnu hyn