TransWikia.com

Distance properties of the permutations of a set of points in a Euclidean space

MathOverflow Asked on November 3, 2021

We are given a set of $n$ distinct points $S={mathbf{x}_1, mathbf{x}_2, ldots, mathbf{x}_n}$ in a Euclidean space $mathbb{R}^d$, where the distance between two points $mathbf{x}_i,mathbf{x}_jin S$ is denoted by $d(i,j)$ for any $i,jin[n]$, and $max_{i,jin [n]}d(i,j)=1$. Let $mathcal{Pi}$ be the set of all functions $pi$ mapping each index of a point of $S$ to a distinct integer in $[n]$, namely a permutation on the indices of the points of $S$. We also define

$$R(pi):=sum_{substack{(i,j,k)in[n]: \pi(i)<pi(j)<pi(k)}} left(1-d(i,j)right)~,$$

$$pi^*:=argmax_{piinmathcal{Pi}} R(pi)~.$$


Question: Can we prove the following conjecture? Does the answer depend on the number of dimensions of the Euclidean space?

For any pair of elements $mathbf{x}_i,mathbf{x}_jin S$ such that $pi^*(i)<pi^*(j)$, the average value of $R(pi)$ over all $piinmathcal{Pi}$ such that $pi(i)<pi(j)$, is greater than or equal to the average value of $R(pi’)$ over all $pi’inmathcal{Pi}$ such that $pi'(i)>pi'(j)$.

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP