On prescribing total preorders and linear orders to pairwise distances of points in Euclidean space

Abstract

We show that any total preorder on a set with $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ elements coincides with the order on pairwise distances of some point collection of size $n$ in ${\mathbb{R}}^{n-1}$. For linear orders, a collection of $n$ points in ${\mathbb{R}}^{n-2}$ suffices. These bounds turn out to be optimal. We also find an optimal bound in a bipartite version for total preorders and a near-optimal bound for a bipartite version for linear orders. Our arguments include tools from convexity and positive semidefinite quadratic forms.

Edit made on February 2026: Corollary 4 is false as stated. The inductive approach fails soon after the inductive base. See page 5 for details on this