Helfgott, Harald Andrés

[["dc.bibliographiccitation.firstpage","1"],["dc.bibliographiccitation.issue","1"],["dc.bibliographiccitation.journal","Journal of Algebraic Combinatorics"],["dc.bibliographiccitation.lastpage","22"],["dc.bibliographiccitation.volume","40"],["dc.contributor.author","Bamberg, John"],["dc.contributor.author","Gill, Nick"],["dc.contributor.author","Hayes, Thomas P."],["dc.contributor.author","Helfgott, Harald Andrés"],["dc.contributor.author","Seress, Ákos"],["dc.contributor.author","Spiga, Pablo"],["dc.date.accessioned","2017-09-07T11:54:20Z"],["dc.date.available","2017-09-07T11:54:20Z"],["dc.date.issued","2013"],["dc.description.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."],["dc.identifier.arxiv","1205.1596"],["dc.identifier.doi","10.1007/s10801-013-0476-3"],["dc.identifier.gro","3146554"],["dc.identifier.uri","https://resolver.sub.uni-goettingen.de/purl?gro-2/4334"],["dc.notes.intern","mathe"],["dc.notes.status","public"],["dc.notes.submitter","chake"],["dc.publisher","Springer Nature"],["dc.relation.eissn","1572-9192"],["dc.relation.issn","0925-9899"],["dc.subject","Cayley graph Diameter Babai’s conjecture Babai-Seress conjecture"],["dc.title","Bounds on the diameter of Cayley graphs of the symmetric group"],["dc.type","journal_article"],["dc.type.internalPublication","unknown"],["dc.type.peerReviewed","no"],["dspace.entity.type","Publication"]]

[["dc.bibliographiccitation.firstpage","611"],["dc.bibliographiccitation.issue","2"],["dc.bibliographiccitation.journal","Annals of Mathematics"],["dc.bibliographiccitation.lastpage","658"],["dc.bibliographiccitation.volume","179"],["dc.contributor.author","Helfgott, Harald Andrés"],["dc.contributor.author","Seress, Ákos"],["dc.date.accessioned","2017-09-07T11:54:20Z"],["dc.date.available","2017-09-07T11:54:20Z"],["dc.date.issued","2014"],["dc.description.abstract","Given a finite group G and a set A of generators, the diameter diam(Γ(G,A)) of the Cayley graph Γ(G,A) is the smallest ℓ such that every element of G can be expressed as a word of length at most ℓ in A∪A−1. We are concerned with bounding diam(G):=maxAdiam(Γ(G,A)). It has long been conjectured that the diameter of the symmetric group of degree n is polynomially bounded in n, but the best previously known upper bound was exponential in nlogn−−−−−√. We give a quasipolynomial upper bound, namely, diam(G)=exp(O((logn)4loglogn))=exp((loglog"],["dc.identifier.doi","10.4007/annals.2014.179.2.4"],["dc.identifier.gro","3146557"],["dc.identifier.uri","https://resolver.sub.uni-goettingen.de/purl?gro-2/4337"],["dc.notes.intern","mathe"],["dc.notes.status","public"],["dc.notes.submitter","chake"],["dc.publisher","Princeton University"],["dc.relation.issn","0003-486X"],["dc.subject","Cayley graphs graph diameters permutation groups"],["dc.title","On the diameter of permutation groups"],["dc.type","journal_article"],["dc.type.internalPublication","unknown"],["dc.type.peerReviewed","no"],["dspace.entity.type","Publication"]]

[["dc.bibliographiccitation.firstpage","349"],["dc.bibliographiccitation.journal","Journal of Algebra"],["dc.bibliographiccitation.lastpage","368"],["dc.bibliographiccitation.volume","421"],["dc.contributor.author","Helfgott, Harald Andrés"],["dc.contributor.author","Seress, Ákos"],["dc.contributor.author","Zuk, Andrzej"],["dc.date.accessioned","2017-09-07T11:54:17Z"],["dc.date.available","2017-09-07T11:54:17Z"],["dc.date.issued","2015"],["dc.identifier.arxiv","1311.6742"],["dc.identifier.gro","3146542"],["dc.identifier.uri","https://resolver.sub.uni-goettingen.de/purl?gro-2/4325"],["dc.notes.intern","Not valid abstract: Let $g$, $h$ be a random pair of generators of $G=Sym(n)$ or $G=Alt(n)$. We show that, with probability tending to $1$ as $n\\\\.o \\\\.infty$, (a) the diameter of $G$ with respect to $S = \\\\.{g,h,g^{-1},h^{-1}\\\\.}$ is at most $O(n^2 (\\\\.log n)^c)$, and (b) the mixing time of $G$ with respect to $S$ is at most $O(n^3 (\\\\.log n)^c)$. (Both $c$ and the implied constants are absolute.) These bounds are far lower than the strongest worst-case bounds known (in Helfgott--Seress, 2013); they roughly match the worst known examples. We also give an improved, though still non-constant, bound on the spectral gap. Our results rest on a combination of the algorithm in (Babai--Beals--Seress, 2004) and the fact that the action of a pair of random permutations is almost certain to act as an expander on $\\\\.ell$-tuples, where $\\\\.ell$ is an arbitrary constant (Friedman et al., 1998)."],["dc.notes.status","public"],["dc.notes.submitter","chake"],["dc.relation.issn","0021-8693"],["dc.title","Random generators of the symmetric group: diameter, mixing time and spectral gap"],["dc.type","journal_article"],["dc.type.internalPublication","unknown"],["dc.type.peerReviewed","no"],["dspace.entity.type","Publication"]]