# Gradient of a function on the vertices of a graph

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 some transposition $\tau$. Consider $f=\left|\sum\limits_{i=1}^na_{\pi(i)}-\sum\limits_{i=n+1}^{2n}a_{\pi(i)}\right|$.

Find $\|\nabla f\|_{\infty}$.

I wasn't sure, but it turns out that this is kind of rephrased question as here question involving Markov chain Thank you.

-

## 1 Answer

As already explained here, that is, on a page you know and should have mentioned, $$\|\nabla f\|_\infty\leqslant2\cdot\max\{|a_i-a_j|\,;\,1\leqslant i\leqslant n,\,n+1\leqslant j\leqslant 2n\}.$$

-
Thank you. First I thought that this ging to be the same, but then I wasn't sure. Now I know:-) –  Nick G.H. Jul 29 '12 at 14:10
I am sorry to asking this question. Its because I just did similar mistake and I wanted to make sure that I understand my mistake now. If I wanted to sum $\|\nabla f\|^2_{\infty}$ over all transpositions $\tau(i,j)$. Would it be the same as to bound it by $4\times 2\sum_{i=1}^n\sum_{j=n+1}^{2n}(a_i-a_j)^2$? (I don't use maximum here). Thank you very much. –  Nick G.H. Aug 2 '12 at 1:01
Let me suggest you show your work--and then we shall have something to discuss. –  Did Aug 2 '12 at 21:25
I've already got an answer for my question. I just was confused with the typo in the answer above. Thank you very much for your help. I really appreciate it:-) –  Nick G.H. Aug 3 '12 at 1:25