Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 0 down vote accepted

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\}. $$

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.