Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
3  
What is the metric on $S_{2m}$? –  scineram Mar 26 '12 at 19:31
    
Sorry, I forgot to mention: the metric on the group of permutations is a counting metric:$\rho_{2m}=\#\{i: \pi_1\neq\pi_2\}$ –  Michael Mar 26 '12 at 20:08

1 Answer 1

up vote 0 down vote accepted

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

share|improve this answer

Your Answer

 
discard

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.