F Nous contacter

Multi angle

H 1 The diameter of the symmetric group: ideas and tools

Auteurs : Helfgott, Harald (Auteur de la Conférence)
CIRM (Editeur )

    Loading the player...

    Résumé : Given a finite group $G$ and a set $A$ of generators, the diameter diam$(\Gamma(G, A))$ of the Cayley graph $\Gamma(G, A)$ is the smallest $\ell$ such that every element of $G$ can be expressed as a word of length at most $\ell$ in $A \cup A^{-1}$. We are concerned with bounding diam$(G) := max_A$ diam$(\Gamma(G, A))$.
    It has long been conjectured that the diameter of the symmetric group of degree $n$ is polynomially bounded in $n$. In 2011, Helfgott and Seress gave a quasipolynomial bound, namely, $O\left (e^{(log n)^{4+\epsilon}}\right )$. We will discuss a recent, much simplified version of the proof.

    Codes MSC :
    05C25 - Graphs and abstract algebra (groups, rings, fields, etc.)
    20B05 - General theory for finite groups
    20B30 - Symmetric groups
    20D60 - Arithmetic and combinatorial problems
    20F69 - asymptotic properties of groups

      Informations sur la Vidéo

      Réalisateur : Hennenfent, Guillaume
      Langue : Anglais
      Date de publication : 06/01/17
      Date de captation : 13/12/16
      Collection : Research talks ; Combinatorics ; Number Theory
      Format : MP4
      Durée : 00:48:04
      Domaine : Combinatorics ; Number Theory
      Audience : Chercheurs ; Doctorants , Post - Doctorants
      Download : https://videos.cirm-math.fr/2016-12-13_Helfgott.mp4

    Informations sur la rencontre

    Nom de la rencontre : Jean-Morlet Chair: Ergodic theory and its connections with arithmetic and combinatorics / Chaire Jean Morlet : Théorie ergodique et ses connexions avec l'arithmétique et la combinatoire
    Organisateurs de la rencontre : Cassaigne, Julien ; Ferenczi, Sébastien ; Hubert, Pascal ; Kulaga-Przymus, Joanna ; Lemanczyk, Mariusz
    Dates : 12/12/16 - 16/12/16
    Année de la rencontre : 2016

    Citation Data

    DOI : 10.24350/CIRM.V.19101303
    Cite this video as: Helfgott, Harald (2016). The diameter of the symmetric group: ideas and tools. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.19101303
    URI : http://dx.doi.org/10.24350/CIRM.V.19101303

    Voir aussi