On prescribing total orders and preorders to pairwise distances of points in Euclidean space. (English) Zbl 1487.52010

Summary: We show that any total preorder on a set of the form \(\begin{pmatrix} X \\ 2 \end{pmatrix}\) where \(X\) has \(n\) elements coincides with the order on pairwise distances of some point collection of size \(n\) in \(\mathbb{R}^{n-1}\). For total 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 total orders. Our arguments include tools from convexity and positive semidefinite quadratic forms.


52A37 Other problems of combinatorial convexity
Full Text: DOI arXiv


[1] Erdös, P., On sets of distances of n points, Am. Math. Mon., 53, 5, 248-250 (1946) · Zbl 0060.34805
[2] Yugai, S., On the largest number of diameters of a point set in Euclidean space, (Investigations in Topological and Generalized Spaces (1988)), 84-87, (in Russian) · Zbl 0734.52005
[3] Martini, H.; Soltan, V., Antipodality properties of finite sets in Euclidean space, Discrete Math., 290, 2, 221-228 (2005) · Zbl 1066.52010
[4] Schoenberg, I., Remarks to Maurice Fréchet’s article ‘Sur la definition axiomatique d’une classe d’espace distances vectoriellement applicable sur l’espace de Hilbert’, Ann. Math., 36, 3, 724-732 (1935)
[5] Matoušek, J., Thirty-Three Miniatures: Mathematical and Algorithmic Applications of Linear Algebra (2010), American Mathematical Society: American Mathematical Society Providence, RI · Zbl 1195.00043
[6] Dekster, B.; Wilker, J., Edge lengths guaranteed to form a simplex, Arch. Math., 49, 351-366 (1987) · Zbl 0608.52007
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.