1
$\begingroup$

I am trying to find the Lipschitz constant for the following function: $ f(\pi)=\left|\sum_{i=1}^{m}c_{\pi(i)}-\sum_{i=m+1}^{2m}c_{\pi(i)}\right|, $ where $c_i \in R$ and $\pi$ is a permutation of the set $\{1,..., 2m\}$ with counting metric $\rho_{2m}=\#\{i: \pi_1(i)\neq \pi_2(i); \pi_1, \pi_2 \in S_{2m}\}$.

I've got Lipschitz constant $2\lVert c\rVert_{\infty}$. I am wondering if one can do something better?

  • 0
    Sorry, I forgot to mention: the metric on the group of permutations is a counting metric:$\rho_{2m}=\#\{i: \pi_1\neq\pi_2\}$2012-03-26

1 Answers 1

0

It seems we can't do better. Consider the case $c_j=\begin{cases}1&\mbox{ if }1\leq j\leq m\\\ -1&\mbox{ if }m+1\leq j\leq 2m \end{cases}$. Then $\lVert c\rVert_{\infty}=1$, $f(\operatorname{Id})=2m$ and if we consider $\pi$ the transposition of $1$ and $m+1$ then $f(\pi)=\left|c_{m+1}+\sum_{j=2}^mc_j-\sum_{j=m+2}^{2m}c_j-c_1\right|=|-1+m-1+(m-1)-1|=2m-4$ so $|f(\operatorname{Id})-f(\pi)|=4=2\rho_{2m}(\operatorname{Id},\pi)\lVert c\rVert_{\infty}$.