I am trying to work on the following exercise.
Suppose $f: (C_n, d_n) \to (\mathbf{R}, |\cdot|)$ is a map of the cycle graph $C_n$ (with nodes labelled, $1, 2, \dots, n$) with the shortest path metric $d_n$ into $\mathbf{R}$ with the usual metric $|\cdot|$. Show that if $f$ is non-expansive, which means $|f(i) - f(j)| \leq d_n(i,j)$ for all $i,j \in \{1, \dots, n\}$, then there exist two nodes $i,j$ for which $$\frac{d_n(i, j)}{|f(i) - f(j)|} = \Omega(n).$$
(By the way $f(n) = \Omega(n)$ means that for all $n$ big enough, $f(n) \geq Cn$, where $C > 0$ is a universal constant.)
I know if you look at an equilateral triangle on the graph, then you can show that the distances contract by at least a constant factor, but I don't know how to go from this to th result, or if this is even helpful.
Put $I=\{1,\dots,n\}$ and $n’\in \{1,\dots,\lfloor n/2\rfloor\}$. We prove a stronger claim: there exist $i,j\in I$ such that $d_n(i,j)=n’$ and $|f(i)-f(j)|\le 1$. For each $i,j\in I$ let $i+’j$ equals $i+j$, if $i+j\le n$, and equals $i+j-n$, otherwise. Remark that $d_n(i, i+’n’)=n’$ for each $i$. Put $I_1=\{i\in I:f(i)\le f(i+’n’)\}$ and $I_2=\{i\in I:f(i)\ge f(i+n’)\}$. Then $I_1\cup I_2$ is a cover of $I$ by its two non-empty subsets. It is easy to see that there exists $i\in I$ such that $i\in I_1$ and $i+1\in I_2$ or $i\in I_2$ and $i+1\in I_1$. Assume that $i\in I_1$ and $i+1\in I_2$. Then $f(i)\le f(i+'n’)$ and $f(i+1)\ge f(i+1+’n’)$. If $f(i)<f(i+'n’)-1$ and $f(i+1)>f(i+1+’n’)+1$ then $f(i+1+’n’)<f(i+1)-1\le f(i)< f(i+'n’)-1$, a contradiction. The case $i\in I_2$ and $i+1\in I_1$ is considered similarly.