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. © 2013 Springer Science+Business Media New York.

Bamberg, J., Gill, N., Hayes, T., Helfgott, H., Seress, Á., & Spiga, P. (2014). Bounds on the diameter of Cayley graphs of the symmetric group. JOURNAL OF ALGEBRAIC COMBINATORICS, 40(1), 1-22 [10.1007/s10801-013-0476-3].

Bounds on the diameter of Cayley graphs of the symmetric group

SPIGA, PABLO
Ultimo
2014

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. © 2013 Springer Science+Business Media New York.
Articolo in rivista - Articolo scientifico
Babai's conjecture; Babai-Seress conjecture; Cayley graph; Diameter; Discrete Mathematics and Combinatorics; Algebra and Number Theory
English
1
22
22
Bamberg, J., Gill, N., Hayes, T., Helfgott, H., Seress, Á., & Spiga, P. (2014). Bounds on the diameter of Cayley graphs of the symmetric group. JOURNAL OF ALGEBRAIC COMBINATORICS, 40(1), 1-22 [10.1007/s10801-013-0476-3].
Bamberg, J; Gill, N; Hayes, T; Helfgott, H; Seress, Á; Spiga, P
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/101349
Citazioni
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 4
Social impact