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)$.
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP