Lengths of tours and permutations on a vertex set of a convex polygon. (Q5954238)

Let \(x_{0},x_{1},\ldots ,x_{n-1}\) be the vertices of a convex \(n\)-gon in the plane, and denote by \(d(i,j)\) the length of the segment \(x_{i}x_{j}\). For any permutation \(\sigma \) of \(\{0,1,\ldots ,n-1\}\), let \(S(\sigma ):=\sum_{i=0}^{n-1}d(i\sigma (i))\), which is called the length of \(\sigma\). The authors consider in particular the permutations \(\sigma _{p}\) defined by \(\sigma _{p}(i):=i+p\bmod n\) and show that \(S(\sigma _{p})\) is a strictly concave and strictly increasing function of \(p\) for \(1\leq p\leq \left\lfloor n/2\right\rfloor \). Furthermore, they show \(S(\sigma _{\left\lfloor n/2\right\rfloor })\geq S(\sigma )\) for all permutations \(\sigma \), and \(S(\sigma _{1})\leq S(\sigma )\) for all conneced permutations \(\sigma \). Here \(\sigma \) is called connected if no proper cyclic interval \([| i,j]| \) is invariant under \(\sigma \). NEWLINENEWLINE(More precisely, \([| i,j]| \) means \(\{i,i+1,\ldots ,j\}\) for \(i, j\), and \(\{i,i+1,\ldots ,n-1,0,1,\ldots ,j\}\) for \(i>j\). A cyclic interval \([| i,j]| \) is called proper if \(j\not\equiv i-1\text{ mod }{}\), which means that it is not equal to \(\{0,1,\ldots ,n-1\}\). It is called invariant under \(\sigma \) if \(\sigma (k)\in [| i,j]| \) for all \(k\in [| i,j]| \). In the paper, the restriction to proper intervals should be added.)