Gradiente de una función en los vértices de un gráfico

Question

Sea $G=(V,E)$ sea un grafo. El gradiente de una función $f:V\longrightarrow R$ se define en las aristas del grafo, dada por la derivada discreta $$ \nabla f(e)=f(y)-f(x), \quad e=(x,y) \in E $$

Toma $V=S_{2n}$ el grupo de permutaciones $\pi$ del conjunto $\{1, \ldots 2n\}$ y $e=(\pi, \pi \tau) \in E$ para alguna transposición $\tau$ . Considere $f=\left|\sum\limits_{i=1}^na_{\pi(i)}-\sum\limits_{i=n+1}^{2n}a_{\pi(i)}\right|$ .

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

No estaba seguro, pero resulta que esto es una especie de pregunta reformulada como aquí pregunta sobre la cadena de Markov Gracias, señor.

Answer 1

Como ya se ha explicado aquí es decir, en una página que usted conoce y debería haber mencionado, $$ \|\nabla f\|_\infty\leqslant2\cdot\max\{|a_i-a_j|\,;\,1\leqslant i\leqslant n,\,n+1\leqslant j\leqslant 2n\}. $$