# spectral gap of the graph / Markov chain

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.

-
Does "some transposition" mean "some given transposition" or "any transposition"? –  joriki Jul 29 '12 at 21:11
@joriki: Thank you. For any transposition. –  Nick G.H. Jul 29 '12 at 21:12