1
$\begingroup$

Let $G=(V,E)$ be a graph. The gradient of a function $f:V\longrightarrow R$ is defined on the edges of the graph, given by the discrete derivative $ \nabla f(e)=f(y)-f(x), \quad e=(x,y) \in E $

Take $V=S_{2n}$ the group of permutations $\pi$ of the set $\{1, \ldots 2n\}$ and $e=(\pi, \pi \tau) \in E$ for any transposition $\tau$.

I am trying to find a lower bound of the spectral gap of the graph $(S_{2n}, E)$. I guess it should be well-known. Any literature would be very helpful.

Thank you.

  • 0
    @joriki: Thank yo$u$. For any transposition.2012-07-29

1 Answers 1

0

Papers by Persi Diaconis and co-authors in general, and in particular Comparison Techniques for Random Walk on Finite Groups, Persi Diaconis and Laurent Saloff-Coste, Ann. Probab. Volume 21, Number 4 (1993), 2131-2156.