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.

Let $P_n$ be group of all permutations of the set $\{1,\dots,n\}$. I have trouble with construction a Lipschitz function $f:P_n \longrightarrow R$.

Any help would be appreciate.

Thank you.

share|improve this question
    
Which metric do you put on $P_n$? –  Davide Giraudo Mar 10 '12 at 22:36
    
The metric is the following: $d_n(p_1, p_2)=\frac 1n \#\{i:p_1(i)\neq p_2(i), \quad p_1, p_2 \in P_n\}$. –  Michael Mar 10 '12 at 22:47
    
how about a constant function? I don't really understand point of question though as $P_n$ is finite. –  ShawnD Mar 10 '12 at 23:01
add comment

2 Answers

up vote 2 down vote accepted

Every function $f$ on a finite metric space $(X,d)$ is Lipschitz.

To wit, call $D$ the minimal distance between distinct points of $X$, and $M$ the diameter of the range of $f$, that is, the maximal difference between the images by $f$ of different points of $X$.

Then, $|f(x)-f(y)|\leqslant (M/D)d(x,y)$ for every $x$ and $y$ in $X$ hence $f$ is Lipschitz on $X$ with constant $M/D$.

share|improve this answer
add comment

$d_n$ is indeed a metric, and we know that if $(X,d)$ is a metric space, for each $x_0\in X$ the map $x\mapsto d(x,x_0)$ is Lipschitz of constant $1$ (it's a consequence of triangular inequality). So for example you can take $f(\sigma):=\frac 1n\operatorname{card}(i:\sigma(i)\neq i)$, or for a fixed permutation $\sigma_0$: $$f_{\sigma_0}(\sigma)=\frac 1n\operatorname{card}(i:\sigma(i)\neq \sigma_0(i)).$$

share|improve this answer
add comment

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.