19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details

Bounds on the diameter of Cayley graphs of the symmetric group

Presented by Dr. Pablo SPIGA
Type: Oral presentation
Track: Cayley Graphs


For a group $G$ and a set $S$ of generators of $G$, the diameter of the {\em Cayley graph} $\Gamma(G,S)$ is the maximum over the group elements $g\in G$ of the shortest expression $g=s_1^{i_1}\cdots s_m^{i_m}$ with $s_k\in S$ and $i_k\in \{-1,1\}$. A first investigation on the diameter of Cayley graphs over groups in general was undertaken by Erd\H{o}s and R\'enyi. Later Babai and Seress obtained asymptotic estimates on the diameter of $\Gamma(G,S)$ depending heavily on the group structure of $G$. In light of these results, Babai and Seress proposed the following conjecture. \smallskip \noindent\textbf{Conjecture. }There exists $c>0$ such that, for a non-abelian simple group $G$ and a set $S$ of generators of $G$, we have $\textrm{diam}(\Gamma(G,S))\leq (\log |G|)^c$. \smallskip In this talk we describe the current state of this conjecture and we present some recent results when $G$ the alternating group.


Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled

Primary authors