Bollobás–Meir TSP Conjecture Holds Asymptotically Alexey Gordeev Abstract In 1992, Bollobás and Meir showed that for every k ≥ 1 k\geq 1 there exists a constant c k c_{k} such that, for any n n points in the k k -dimensional unit cube [ 0 , 1 ] k [0,1]^{k} , one can find a tour x 1 , … , x n x_{1},\dots,x_{n} through these n n points with ∑ i = 1 n | x i − x i + 1 | k ≤ c k \sum_{i=1}^{n}|x_{i}-x_{i+1}|^{k}\leq c_{k} , where x n + 1 = x 1 x_{n+1}=x_{1} and | x − y | |x-y| is the Euclidean distance between x x and y y . Remarkably, this bound does not depend on n n , the number of points. They conjectured that the optimal constant is c k = 2 ⋅ k k / 2 c_{k}=2\cdot k^{k/2} and showed that it cannot be taken lower than that. This conjecture was recently revised for k = 3 k=3 by Balogh, Clemen and Dumitrescu, who showed that c 3 ≥ 2 7 / 2 > 2 ⋅ 3 3 / 2 c_{3}\geq 2^{7/2}>2\cdot 3^{3/2} . It remains open for all k > 2 k>2 , with the best known upper bound c k ≤ 2.65 k ⋅ k k / 2 ⋅ ( 1 + o k ​ ( 1 ) ) c_{k}\leq 2.65^{k}\cdot k^{k/2}\cdot(1+o_{k}(1)) . We significantly narrow the gap between lower and upper bounds on c k c_{k} , reducing it from exponential to linear. Specifically, we prove that c k ≤ 2 ​ e ​ ( k + 1 ) ⋅ k k / 2 c_{k}\leq 2\mathrm{e}(k+1)\cdot k^{k/2} and c k = k k / 2 ⋅ ( 2 + o k ​ ( 1 ) ) c_{k}=k^{k/2}\cdot(2+o_{k}(1)) , the latter establishing the conjecture asymptotically. We also obtain analogous results for related problems on Hamiltonian paths, spanning trees and perfect matchings in the unit cube. Our main tool is a new generalization of the ball packing argument used in earlier works. 1 Introduction Throughout the text, k is a positive integer. For points \mathbf{a}=(a_{1},\dots,a_{k}),\mathbf{b}=(b_{1},\dots,b_{k})\in{\mathbb{R}}^{k} denote by \langle\mathbf{a},\mathbf{b}\rangle:=\sum_{i=1}^{k}a_{i}b_{i} their dot product, and by |\mathbf{a}|:=\sqrt{\langle\mathbf{a},\mathbf{a}\rangle} the Euclidean length of \mathbf{a} . For a finite set X\subseteq{\mathbb{R}}^{k} , let K(X) be the complete graph on the vertex set X . We will say that E is a set of edges on X if E is a subset of the set of edges of K(X) . Similarly, we will say that E is a Hamiltonian cycle on X if it is a Hamiltonian cycle in K(X) . For a set E of edges on X and an edge e=\mathbf{a}\mathbf{b}\in E , denote by |e|:=|\mathbf{a}-\mathbf{b}| the Euclidean distance between endpoints of e , and for a positive integer t define S_{t}(E):=\sum_{e\in E}|e|^{t} . The following theorem is due to Newman [ 10 , Problem 57] . Theorem 1.1 (Newman) . For any finite set X\subseteq[0,1]^{2} of points in the unit square, there exists a Hamiltonian cycle H on X with S_{2}(H)=\sum_{e\in H}|e|^{2}\leq 4. Notably, this bound does not depend on the size of the set X . Point sets in Figure 1 show that the constant 4 is best possible. In 1987, Meir [ 9 , Remark (ii)] asked for a higher-dimensional analogue of Theorem 1.1 , which was given a few years later by Bollobás and Meir [ 4 , Theorem 3] . \sqrt{2} 1 1 \sqrt{2} 1 1 1 1 1 1 1 \frac{\sqrt{2}}{2} \frac{\sqrt{2}}{2} 2\cdot(\sqrt{2})^{2}=4 (\sqrt{2})^{2}+2\cdot 1^{2}=4 4\cdot 1^{2}=4 2\cdot\left(\frac{\sqrt{2}}{2}\right)^{2}+3\cdot 1^{2}=4 Figure 1: Point sets attaining the upper bound in Theorem 1.1 . Theorem 1.2 (Bollobás and Meir) . For any finite set X\subseteq[0,1]^{k} of points in the k -dimensional unit cube, there exists a Hamiltonian cycle H on X with S_{k}(H)=\sum_{e\in H}|e|^{k}\leq\frac{2}{3}\cdot 9^{k}\cdot k^{k/2}. Similar to Theorem 1.1 , the upper bound in Theorem 1.2 does not depend on the number of points in X , only on the dimension k . For a finite set X\subseteq{\mathbb{R}}^{k} , let S_{k}^{\mathrm{HC}}(X):=\min_{H}S_{k}(H) , where the minimum is over all Hamiltonian cycles H on X , and let S_{k}^{\mathrm{HC}}:=\sup\left\{S_{k}^{\mathrm{HC}}(X)\,:\,X\subseteq[0,1]^{k},\ X\text{ is a finite set}\right\}. Let S_{k}^{\mathrm{HP}}(X) and S_{k}^{\mathrm{HP}} , S_{k}^{\mathrm{ST}}(X) and S_{k}^{\mathrm{ST}} , S_{k}^{\mathrm{PM}}(X) and S_{k}^{\mathrm{PM}} be defined similarly for, respectively, Hamiltonian paths , spanning trees and perfect matchings instead of Hamiltonian cycles, with only even-sized sets X allowed in the definitions of S_{k}^{\mathrm{PM}}(X) and S_{k}^{\mathrm{PM}} . Remark 1.3 . Related works often used notation like s_{k}(E):=(S_{k}(E))^{\frac{1}{k}} and s_{k}^{\mathrm{HC}}(X):=(S_{k}^{\mathrm{HC}}(X))^{\frac{1}{k}} to avoid dealing with exponents in bounds. We find using S_{k} directly more convenient, in particular when discussing the new results of this paper. To keep notation consistent, we state all results, old and new, in terms of S_{k} . Example 1.4 . Let X=\{\mathbf{0},\mathbf{1}\}\subseteq[0,1]^{k} , where \mathbf{0}=(0,\dots,0) and \mathbf{1}=(1,\dots,1) . Then S_{k}^{\mathrm{HC}}\geq S_{k}^{\mathrm{HC}}(X)=2\cdot k^{k/2},\quad S_{k}^{\mathrm{HP}}\geq S_{k}^{\mathrm{HP}}(X)=k^{k/2},\quad S_{k}^{\mathrm{ST}}\geq S_{k}^{\mathrm{ST}}(X)=k^{k/2},\quad S_{k}^{\mathrm{PM}}\geq S_{k}^{\mathrm{PM}}(X)=k^{k/2}. Combining Theorem 1.2 and Example 1.4 , we see that 2\cdot k^{k/2}\leq S_{k}^{\mathrm{HC}}\leq\frac{2}{3}\cdot 9^{k}\cdot k^{k/2}. (1) In the conclusion of their paper [ 4 ] , Bollobás and Meir conjectured that S_{k}^{\mathrm{HC}}=2\cdot k^{k/2} for all k . The case k=1 is trivial, and due to Theorem 1.1 , this is also true for k=2 . The exact value of S_{k}^{\mathrm{HC}} is not known for any k>2 . Recently, Balogh, Clemen and Dumitrescu [ 2 , Theorem 1.3(i)] disproved the conjecture for k=3 by presenting the following example. Example 1.5 (Balogh, Clemen and Dumitrescu) . Let X=\{(0,0,0),(0,1,1),(1,0,1),(1,1,0)\}\subseteq[0,1]^{3} . Then S^{\mathrm{HC}}_{3}\geq S^{\mathrm{HC}}_{3}(X)=4\cdot 2^{3/2}>2\cdot 3^{3/2}. They proposed an adjusted conjecture [ 2 , Conjecture 5.5] , which remains open for all k>2 . Conjecture 1.6 (Bollobás–Meir conjecture) . For any finite set of points X\subseteq[0,1]^{k} , there exists a Hamiltonian cycle H on X with S_{k}(H)\leq 2\cdot k^{k/2} if k\neq 3 , and S_{3}(H)\leq 2^{7/2} if k=3 . In other words, S_{k}^{\mathrm{HC}}=\begin{cases}2\cdot k^{k/2}&\text{for }k\neq 3,\\ 2^{7/2}&\text{for }k=3.\end{cases} Theorem 1.2 is a direct consequence of two inequalities: S_{k}^{\mathrm{HC}}\leq\frac{2}{3}\cdot 3^{k}\cdot S_{k}^{\mathrm{ST}}\quad\text{and}\quad S_{k}^{\mathrm{ST}}\leq 3^{k}\cdot k^{k/2}. (2) The first inequality follows by approximating a Hamiltonian cycle with a spanning tree, using ideas first developed by Sekanina [ 13 , 14 ] in the 60s. The second inequality is obtained via a ball packing argument: one can show that placing a ball of radius \frac{|e|}{4} on the center of each edge e of the minimal spanning tree yields a collection of disjoint balls, and the inequality follows by bounding their total volume. Although the upper bound in Theorem 1.2 has since been improved, subsequent works continued to rely on the same combination of ball packing arguments and approximation techniques. In [ 6 , Theorems 3.4 and 5.2] , the present author used refined variants of the ball packing argument to obtain the best exact upper bounds to date for S_{k}^{\mathrm{ST}} and S_{k}^{\mathrm{PM}} : S_{k}^{\mathrm{ST}}\leq 2\cdot 1.823^{k}\cdot k^{k/2}\quad\text{and}\quad S_{k}^{\mathrm{PM}}\leq 2\cdot(\sqrt{2})^{k}\cdot k^{k/2}. These bounds, together with approximation ideas in the vein of the Christofides algorithm [ 5 ] for the metric travelling salesman problem, led to the best exact upper bound to date for S_{k}^{\mathrm{HC}} [ 6 , Theorem 6.1] : S_{k}^{\mathrm{HC}}\leq 1.28\cdot 5.059^{k}\cdot k^{k/2}. Balogh, Clemen and Dumitrescu [ 2 , Theorem 1.5] established by asymptotic analysis of a certain greedy algorithm (which we will revisit in Section 5 ), that for large k , S_{k}^{\mathrm{ST}}\leq k^{k/2}\cdot(1+o_{k}(1)). Note that, in view of Example 1.4 , this is asymptotically optimal. Using approximation, they also obtained an asymptotic upper bound on S_{k}^{\mathrm{HC}} , which was later improved [ 6 , Theorem 6.2] to S_{k}^{\mathrm{HC}}\leq 2.65^{k}\cdot k^{k/2}\cdot(1+o_{k}(1)). 1.1 New results The main contribution of this work is a new generalization of the ball packing argument. The key idea is to allow balls to intersect in a controlled manner instead of requiring them to be disjoint. This not only leads to improved bounds but, more importantly, allows for direct application to Hamiltonian cycles, eliminating the need for approximation. As a result, we can show that the Conjecture 1.6 (Bollobás–Meir conjecture) . holds asymptotically. Theorem 1.7 . For any finite set X\subseteq[0,1]^{k} , there exists a Hamiltonian cycle H on X such that, if e_{1},e_{2}\in H are two longest edges of H , then \sum_{e\in H\setminus\{e_{1},e_{2}\}}|e|^{k}=o_{k}(k^{k/2}),\quad\text{so}\quad S_{k}(H)=\sum_{e\in H}|e|^{k}\leq k^{k/2}\cdot(2+o_{k}(1)). In particular, S_{k}^{\mathrm{HC}}=k^{k/2}\cdot(2+o_{k}(1)). Theorem 1.7 is a direct corollary of the following result for Hamiltonian paths, which asserts that Conjecture 5.6 in [ 2 ] , the analogue of the Conjecture 1.6 (Bollobás–Meir conjecture) . for Hamiltonian paths, also holds asymptotically. Theorem 1.8 . For any finite set X\subseteq[0,1]^{k} , there exists a Hamiltonian path P on X such that, if e_{1}\in P is the longest edge of P , then \sum_{e\in P\setminus\{e_{1}\}}|e|^{k}=o_{k}(k^{k/2}),\quad\text{so}\quad S_{k}(P)=\sum_{e\in P}|e|^{k}\leq k^{k/2}\cdot(1+o_{k}(1)). In particular, S_{k}^{\mathrm{HP}}=k^{k/2}\cdot(1+o_{k}(1)). Proof of Theorem 1.7 using Theorem 1.8 . For a finite set X\subseteq[0,1]^{k} , let the Hamiltonian path P from Theorem 1.8 have endpoints \mathbf{a},\mathbf{b}\in X . Then H:=P\cup\{\mathbf{a}\mathbf{b}\} is the desired Hamiltonian cycle. ∎ Informally speaking, Theorems 1.7 and 1.8 imply that for large k the points of an extremal set X\subseteq[0,1]^{k} with S_{k}^{\mathrm{HC}}(X)=k^{k/2}\cdot(2+o_{k}(1)) (or S_{k}^{\mathrm{HP}}(X)=k^{k/2}\cdot(1+o_{k}(1)) ) must be clustered around two opposite vertices of the unit cube [0,1]^{k} . Turning to exact bounds, we prove the following theorem, bringing the upper bound on S_{k}^{\mathrm{HC}} within a linear factor of the lower bound of Example 1.4 . Theorem 1.9 . For any finite set X\subseteq[0,1]^{k} , there exists a Hamiltonian cycle H on X such that 1. for any integer t\geq 1 , S_{k}(H)=\sum_{e\in H}|e|^{k}\leq 2(2t+1)\cdot\left(1+\frac{1}{t}\right)^{k/2}\cdot k^{k/2} ; 2. S_{k}(H)\leq 2\mathrm{e}(k+1)\cdot k^{k/2} , where \mathrm{e}=2.718.. is Euler’s number. In particular, S_{k}^{\mathrm{HC}}\leq 2\mathrm{e}(k+1)\cdot k^{k/2}. Any Hamiltonian cycle on a finite set X contains a Hamiltonian path on X as a subset. Any Hamiltonian path on X is a spanning tree on X , and contains a perfect matching on X as a subset when |X| is even. Thus, Theorems 1.8 and 1.9 immediately imply the following new upper bounds. Corollary 1.10 . The following hold, where \mathrm{e}=2.718.. is Euler’s number: 1. S_{k}^{\mathrm{HP}},S_{k}^{\mathrm{ST}}\leq 2\mathrm{e}(k+1)\cdot k^{k/2} ; 2. S_{k}^{\mathrm{PM}}=k^{k/2}\cdot(1+o_{k}(1)) . For perfect matchings, we show an exact upper bound stronger than those implied by Theorem 1.9 . Theorem 1.11 . For any set X\subseteq[0,1]^{k} of even size, there exists a perfect matching M on X such that S_{k}(M)\leq 2(k+1)\cdot k^{k/2} . In other words, S_{k}^{\mathrm{PM}}\leq 2(k+1)\cdot k^{k/2}. 1.2 Overview The rest of the paper is organized as follows. In Section 2 , we present a new generalized ball packing lemma. We begin by applying it to the setting of perfect matchings, proving Theorem 1.11 in Section 3 using classical results of Rankin [ 12 ] on the maximal size of spherical codes with negative dot products. In Section 4 , we turn to Hamiltonian cycles, proving Theorem 1.9 via an alternative approach based on properties of centroids of finite point sets. In Section 5 , we adapt the asymptotic analysis of [ 2 , Section 4] to establish Theorem 1.8 . Finally, Section 6 concludes with a discussion of related questions. 2 Half-ball t -fold packing lemma Denote the open ball of radius r\geq 0 centered at \mathbf{a}\in{\mathbb{R}}^{k} by \B_{r}(\mathbf{a}):=\{\mathbf{x}\in{\mathbb{R}}^{k}\,:\,|\mathbf{x}-\mathbf{a}|1 in this context is new. We will see in the next section that increasing t often allows to obtain t -fold packings \mathfrak{B}_{\alpha}^{E} with comparatively larger \alpha on the same edge set E , leading to exponential improvements in the upper bound ( 3 ) on S_{k}(E) . In Section 4 , we will show that \mathfrak{B}_{\alpha}^{H} is a t -fold packing for a careful choice of t>1 , \alpha and a Hamiltonian cycle H on a given point set X . This allows to apply Lemma 2.3 in the case of Hamiltonian cycles directly, without first approximating a Hamiltonian cycle with a less complex edge structure. 3 Perfect matchings The goal of this section is to prove Theorem 1.11 . We already have the first ingredient, Lemma 2.3 . To complete the proof, for any point set X\subseteq[0,1]^{k} of even size, it would suffice to find a perfect matching M on X such that \mathfrak{B}_{\alpha}^{M} is a t -fold packing for some appropriate t and \alpha . Restricting ourselves for a moment to the case t=1 , note that \mathfrak{B}_{\alpha}^{M} is a packing if and only if for any e=\mathbf{a}\mathbf{b},f=\mathbf{c}\mathbf{d}\in M , the inequality |\mathbf{m}_{e}-\mathbf{m}_{f}|\geq\alpha(|e|+|f|) holds. We can express the distance |\mathbf{m}_{e}-\mathbf{m}_{f}| in terms of distances between points \mathbf{a},\mathbf{b},\mathbf{c},\mathbf{d} using the following classical formula for the length of a bimedian of a tetrahedron (see, for example, the textbook of Altshiller-Court [ 1 , page 56] ). Lemma 3.1 . For any \mathbf{a},\mathbf{b},\mathbf{c},\mathbf{d}\in{\mathbb{R}}^{k} , \left|\frac{\mathbf{a}+\mathbf{b}}{2}-\frac{\mathbf{c}+\mathbf{d}}{2}\right|^{2}=\frac{|\mathbf{a}-\mathbf{c}|^{2}+|\mathbf{b}-\mathbf{d}|^{2}+|\mathbf{a}-\mathbf{d}|^{2}+|\mathbf{b}-\mathbf{c}|^{2}-|\mathbf{a}-\mathbf{b}|^{2}-|\mathbf{c}-\mathbf{d}|^{2}}{4}. Proof. Both sides are equal to \frac{|\mathbf{a}|^{2}+|\mathbf{b}|^{2}+|\mathbf{c}|^{2}+|\mathbf{d}|^{2}}{4}+\frac{\langle\mathbf{a},\mathbf{b}\rangle+\langle\mathbf{c},\mathbf{d}\rangle-\langle\mathbf{a},\mathbf{c}\rangle-\langle\mathbf{b},\mathbf{d}\rangle-\langle\mathbf{a},\mathbf{d}\rangle-\langle\mathbf{b},\mathbf{c}\rangle}{2}.\qed The following key lemma for perfect matchings easily follows from this formula. Lemma 3.2 . Let X\subseteq{\mathbb{R}}^{k} be a set of even size, and let M be a perfect matching on X with minimal possible S_{2}(M) . Then, for any e,f\in M , |\mathbf{m}_{e}-\mathbf{m}_{f}|^{2}\geq\frac{|e|^{2}+|f|^{2}}{4}. Proof. Denote e=\mathbf{a}\mathbf{b} , f=\mathbf{c}\mathbf{d} , M_{1}:=(M\setminus\{e,f\})\cup\{\mathbf{a}\mathbf{c},\mathbf{b}\mathbf{d}\} , M_{2}:=(M\setminus\{e,f\})\cup\{\mathbf{a}\mathbf{d},\mathbf{b}\mathbf{c}\} . Note that M_{1} and M_{2} are also perfect matchings on X , thus S_{2}(M_{1})\geq S_{2}(M) and S_{2}(M_{2})\geq S_{2}(M) , or |\mathbf{a}-\mathbf{c}|^{2}+|\mathbf{b}-\mathbf{d}|^{2}\geq|e|^{2}+|f|^{2}\quad\text{and}\quad|\mathbf{a}-\mathbf{d}|^{2}+|\mathbf{b}-\mathbf{c}|^{2}\geq|e|^{2}+|f|^{2}. Then, by Lemma 3.1 , |\mathbf{m}_{e}-\mathbf{m}_{f}|^{2}=\frac{|\mathbf{a}-\mathbf{c}|^{2}+|\mathbf{b}-\mathbf{d}|^{2}+|\mathbf{a}-\mathbf{d}|^{2}+|\mathbf{b}-\mathbf{c}|^{2}-|e|^{2}-|f|^{2}}{4}\geq\frac{|e|^{2}+|f|^{2}}{4}.\qed Combining Lemma 3.2 with the inequality |e|^{2}+|f|^{2}\geq\frac{(|e|+|f|)^{2}}{2} , we see that the set \mathfrak{B}_{\alpha}^{M} is a packing for \alpha=\frac{1}{\sqrt{8}} and any S_{2} -minimal perfect matching M on X . Together with Lemma 2.3 , this implies S_{k}^{\mathrm{PM}}\leq 2\cdot(\sqrt{2})^{k}\cdot k^{k/2} , see [ 6 , Theorem 3.4] . However, we can get a much stronger bound by considering t -fold packings with t>1 instead. Namely, we will show that, under the same assumptions as in Lemma 3.2 , \mathfrak{B}_{1/2}^{M} is a (k+1) -fold packing, using properties of spherical codes with negative dot products. We will also investigate an alternative approach in Section 4 . Let \mathrm{S}_{k} denote the unit sphere in k dimensions centered at the origin, that is, \mathrm{S}_{k}:=\{\mathbf{x}\in{\mathbb{R}}^{k}\,:\,|\mathbf{x}|=1\} . A (k,n,s) - spherical code of dimension k , size n and maximum dot product s is a set of n points X\subseteq\mathrm{S}_{k} with \langle\mathbf{x},\mathbf{y}\rangle\leq s for any distinct \mathbf{x},\mathbf{y}\in X . Rankin [ 12 ] determined the maximal possible size n of a (k,n,s) -spherical code when s\leq 0 . For convenience, we state this result in the following form, which is directly implied by [ 12 , Theorem 1] . Lemma 3.3 (Rankin) . A (k,n,s) -spherical code with s<0 has n\leq k+1 . Proposition 3.4 . Let X\subseteq{\mathbb{R}}^{k} be a set of even size, and let M be a perfect matching on X with minimal possible S_{2}(M) . Then \mathfrak{B}_{1/2}^{M} is a (k+1) -fold packing. Proof. Fix any point \mathbf{x}\in{\mathbb{R}}^{k} and let it be contained in the ball \B_{1/2}^{e_{i}} for n distinct edges e_{1},\dots,e_{n}\in M , i.e. |\mathbf{m}_{e_{i}}-\mathbf{x}|^{2}<|e_{i}|^{2}/4 for 1\leq i\leq n . Due to Lemma 3.2 , for any i\neq j we have |\mathbf{m}_{e_{i}}-\mathbf{m}_{e_{j}}|^{2}\geq\frac{|e_{i}|^{2}+|e_{j}|^{2}}{4}>|\mathbf{m}_{e_{i}}-\mathbf{x}|^{2}+|\mathbf{m}_{e_{j}}-\mathbf{x}|^{2}, therefore \langle\mathbf{m}_{e_{i}}-\mathbf{x},\mathbf{m}_{e_{j}}-\mathbf{x}\rangle=\frac{|\mathbf{m}_{e_{i}}-\mathbf{x}|^{2}+|\mathbf{m}_{e_{j}}-\mathbf{x}|^{2}-|(\mathbf{m}_{e_{i}}-\mathbf{x})-(\mathbf{m}_{e_{j}}-\mathbf{x})|^{2}}{2}<0. Then the set \left\{\frac{\mathbf{m}_{e_{i}}-\mathbf{x}}{|\mathbf{m}_{e_{i}}-\mathbf{x}|}\,:\,1\leq i\leq n\right\} is a (k,n,s) -spherical code for some s<0 , thus n\leq k+1 by Lemma 3.3 . ∎ Proof of Theorem 1.11 . After a parallel translation, we may assume that X\subseteq\left[-\frac{1}{2},\frac{1}{2}\right]^{k} . Let M be a perfect matching on X which minimizes S_{2}(M) . Due to Proposition 3.4 , \mathfrak{B}_{1/2}^{M} is a (k+1) -fold packing, then so is \mathfrak{hB}_{1/2}^{M} . Applying Lemma 2.3 with E=M , t=k+1 and \alpha=\frac{1}{2} , we get S_{k}(M)\leq\frac{2(k+1)}{\left(2\cdot\frac{1}{2}\right)^{k}}\cdot k^{k/2}=2(k+1)\cdot k^{k/2}.\qed 4 Hamiltonian cycles At first glance, proving an analogue of Lemma 3.2 for Hamiltonian cycles seems impossible, since the midpoints of two edges of an (even optimal) cycle can be arbitrarily close to each other, or even coincide as in Example 1.4 . However, it turns out that such an analogue exists if one considers four edges instead of two. Lemma 4.1 . Let X\subseteq{\mathbb{R}}^{k} and let H be a Hamiltonian cycle on X with minimal possible S_{2}(H) . Then, for any four edges e_{1},e_{2},e_{3},e_{4}\in H , numbered in the order in which they appear on the cycle, |\mathbf{m}_{e_{1}}-\mathbf{m}_{e_{3}}|^{2}+|\mathbf{m}_{e_{2}}-\mathbf{m}_{e_{4}}|^{2}\geq\frac{|e_{1}|^{2}+|e_{2}|^{2}+|e_{3}|^{2}+|e_{4}|^{2}}{4}. Proof. Let F:=\{e_{1},e_{2},e_{3},e_{4}\} , e_{i}=\mathbf{a}_{i}\mathbf{b}_{i} , 1\leq i\leq 4 , such that H=F\cup P_{\mathbf{b}_{1}\mathbf{a}_{2}}\cup P_{\mathbf{b}_{2}\mathbf{a}_{3}}\cup P_{\mathbf{b}_{3}\mathbf{a}_{4}}\cup P_{\mathbf{b}_{4}\mathbf{a}_{1}} , where P_{\mathbf{x}\mathbf{y}} is a (possibly empty) path with endpoints \mathbf{x} and \mathbf{y} , see Figure 2 (left). Denote F_{1}:=\{\mathbf{a}_{1}\mathbf{a}_{3},\mathbf{b}_{1}\mathbf{b}_{3},\mathbf{a}_{2}\mathbf{b}_{4},\mathbf{b}_{2}\mathbf{a}_{4}\} , F_{2}:=\{\mathbf{a}_{1}\mathbf{b}_{3},\mathbf{b}_{1}\mathbf{a}_{3},\mathbf{a}_{2}\mathbf{a}_{4},\mathbf{b}_{2}\mathbf{b}_{4}\} , H_{1}:=(H\setminus F)\cup F_{1} and H_{2}:=(H\setminus F)\cup F_{2} . Note that H_{1} and H_{2} are also Hamiltonian cycles on X , see Figure 2 (center and right). It follows that S_{2}(H_{1})\geq S_{2}(H) and S_{2}(H_{2})\geq S_{2}(H) , thus S_{2}(F_{1})\geq S_{2}(F) and S_{2}(F_{2})\geq S_{2}(F) . \phantom{|}\mathbf{a}_{1} \phantom{|}\mathbf{b}_{1} \phantom{|}\mathbf{a}_{2}\phantom{|} \phantom{|}\mathbf{b}_{2}\phantom{|} \mathbf{a}_{3}\phantom{|} \mathbf{b}_{3}\phantom{|} \phantom{|}\mathbf{a}_{4}\phantom{|} \phantom{|}\mathbf{b}_{4}\phantom{|} \phantom{|}\mathbf{a}_{1} \phantom{|}\mathbf{b}_{1} \phantom{|}\mathbf{a}_{2}\phantom{|} \phantom{|}\mathbf{b}_{2}\phantom{|} \mathbf{a}_{3}\phantom{|} \mathbf{b}_{3}\phantom{|} \phantom{|}\mathbf{a}_{4}\phantom{|} \phantom{|}\mathbf{b}_{4}\phantom{|} \phantom{|}\mathbf{a}_{1} \phantom{|}\mathbf{b}_{1} \phantom{|}\mathbf{a}_{2}\phantom{|} \phantom{|}\mathbf{b}_{2}\phantom{|} \mathbf{a}_{3}\phantom{|} \mathbf{b}_{3}\phantom{|} \phantom{|}\mathbf{a}_{4}\phantom{|} \phantom{|}\mathbf{b}_{4}\phantom{|} H H_{1} H_{2} Figure 2: Hamiltonian cycles differing only in edges with both endpoints in \{\mathbf{a}_{1},\mathbf{b}_{1},\mathbf{a}_{2},\mathbf{b}_{2},\mathbf{a}_{3},\mathbf{b}_{3},\mathbf{a}_{4},\mathbf{b}_{4}\} . Applying Lemma 3.1 two times, for points \mathbf{a}_{1},\mathbf{b}_{1},\mathbf{a}_{3},\mathbf{b}_{3} , and for points \mathbf{a}_{2},\mathbf{b}_{2},\mathbf{a}_{4},\mathbf{b}_{4} , we get |\mathbf{m}_{e_{1}}-\mathbf{m}_{e_{3}}|^{2}+|\mathbf{m}_{e_{2}}-\mathbf{m}_{e_{4}}|^{2}=\frac{S_{2}(F_{1})+S_{2}(F_{2})-S_{2}(F)}{4}\geq\frac{S_{2}(F)}{4}=\frac{|e_{1}|^{2}+|e_{2}|^{2}+|e_{3}|^{2}+|e_{4}|^{2}}{4}.\qed As a consequence of Lemma 4.1 , under the same notation, either |\mathbf{m}_{e_{1}}-\mathbf{m}_{e_{3}}|^{2}\geq\frac{|e_{1}|^{2}+|e_{3}|^{2}}{4} , or |\mathbf{m}_{e_{2}}-\mathbf{m}_{e_{4}}|^{2}\geq\frac{|e_{2}|^{2}+|e_{4}|^{2}}{4} , i.e. either |\mathbf{m}_{e_{1}}-\mathbf{m}_{e_{3}}|\geq\frac{|e_{1}|+|e_{3}|}{\sqrt{8}} , or |\mathbf{m}_{e_{2}}-\mathbf{m}_{e_{4}}|\geq\frac{|e_{2}|+|e_{4}|}{\sqrt{8}} . It follows that \mathfrak{B}_{\alpha}^{H} is a 3-fold packing for \alpha=\frac{1}{\sqrt{8}} and any S_{2} -minimal Hamiltonian cycle H on X . Combining this with Lemma 2.3 , we already get S_{k}^{\mathrm{HC}}\leq 6\cdot 2^{k/2}\cdot k^{k/2} , which is exponentially stronger than all previously known upper bounds on S_{k}^{\mathrm{HC}} , including the asymptotic ones. As in previous section, by considering t -fold packings with larger t , we can push this even further. One way to do this is to apply Lemma 3.3 again. However, we prove Theorem 1.9 by an alternative and, in a sense, more elementary approach. Stated in the form of the following lemma, it uses properties of centroids of finite point sets. For the sake of completeness, in Appendix A we give alternative proofs of exact upper bounds on S_{k}^{\mathrm{HC}} using Lemma 3.3 , and on S_{k}^{\mathrm{PM}} using Lemma 4.2 . Both turn out to be somewhat weaker than Theorems 1.9 and 1.11 . Lemma 4.2 . Let n\geq 1 and \mathbf{a}_{1},\dots,\mathbf{a}_{n}\subseteq{\mathbb{R}}^{k} . For any \mathbf{x}\in{\mathbb{R}}^{k} , \sum_{i=1}^{n}|\mathbf{a}_{i}-\mathbf{x}|^{2}\geq\frac{1}{n}\sum_{i\alpha\sqrt{k} for every two distinct points \mathbf{u},\mathbf{v}\in Y . Then |Y|\cdot\alpha^{k}\leq 0.999^{k} . For a finite set X\subseteq{\mathbb{R}}^{k} , we will call a set E of edges on X a path family of size m if |E|=m and E is a union of one or several vertex-disjoint paths. Remark 5.3 . Hamiltonian paths on X are precisely path families on X of size |X|-1 . More generally, for a Hamiltonian cycle H on X , any subset E\subsetneq H with |E|=m<|X| is a path family on X of size m . Arguments used in Section 4 for Hamiltonian cycles can be applied with minimal changes to path families of a fixed size. In particular, we could prove an analogue of Proposition 4.3 for path families of a fixed size. For our purposes, however, the following would suffice. Proposition 5.4 . Let X\subseteq{\mathbb{R}}^{k} and let E be a path family of size m on X with minimal S_{2}(E) among all path families of size m on X . Then \mathfrak{B}_{1/\sqrt{8}}^{E} is a 3-fold packing. Proof. Let H be any Hamiltonian cycle on X such that E\subseteq H . Let e_{1},e_{2},e_{3},e_{4}\in E be any four distinct edges of E , numbered in the order in which they appear on the cycle H . It is sufficient to show that the balls \B_{1/\sqrt{8}}^{e_{i}} and \B_{1/\sqrt{8}}^{e_{j}} are disjoint for some i\neq j . Let F:=\{e_{1},e_{2},e_{3},e_{4}\} , e_{i}=\mathbf{a}_{i}\mathbf{b}_{i} , 1\leq i\leq 4 , such that H=F\cup P_{\mathbf{b}_{1}\mathbf{a}_{2}}\cup P_{\mathbf{b}_{2}\mathbf{a}_{3}}\cup P_{\mathbf{b}_{3}\mathbf{a}_{4}}\cup P_{\mathbf{b}_{4}\mathbf{a}_{1}} , where P_{\mathbf{x}\mathbf{y}} is a (possibly empty) path with endpoints \mathbf{x} and \mathbf{y} . Denote F_{1}:=\{\mathbf{a}_{1}\mathbf{a}_{3},\mathbf{b}_{1}\mathbf{b}_{3},\mathbf{a}_{2}\mathbf{b}_{4},\mathbf{b}_{2}\mathbf{a}_{4}\} , F_{2}:=\{\mathbf{a}_{1}\mathbf{b}_{3},\mathbf{b}_{1}\mathbf{a}_{3},\mathbf{a}_{2}\mathbf{a}_{4},\mathbf{b}_{2}\mathbf{b}_{4}\} , H_{1}:=(H\setminus F)\cup F_{1} and H_{2}:=(H\setminus F)\cup F_{2} . Since H_{1} and H_{2} are also Hamiltonian cycles on X (see Figure 2 ), by Remark 5.3 , it follows that E_{1}:=(E\setminus F)\cup F_{1}\subseteq H_{1} and E_{2}:=(E\setminus F)\cup F_{2}\subseteq H_{2} are path families on X of size m . Then S_{2}(E_{1})\geq S_{2}(E) and S_{2}(E_{2})\geq S_{2}(E) , so S_{2}(F_{1})\geq S_{2}(F) and S_{2}(F_{2})\geq S_{2}(F) . Applying Lemma 3.1 two times, for points \mathbf{a}_{1},\mathbf{b}_{1},\mathbf{a}_{3},\mathbf{b}_{3} , and for points \mathbf{a}_{2},\mathbf{b}_{2},\mathbf{a}_{4},\mathbf{b}_{4} , we get |\mathbf{m}_{e_{1}}-\mathbf{m}_{e_{3}}|^{2}+|\mathbf{m}_{e_{2}}-\mathbf{m}_{e_{4}}|^{2}=\frac{S_{2}(F_{1})+S_{2}(F_{2})-S_{2}(F)}{4}\geq\frac{S_{2}(F)}{4}=\frac{|e_{1}|^{2}+|e_{2}|^{2}+|e_{3}|^{2}+|e_{4}|^{2}}{4}. Then, either for i=1 and j=3 , or for i=2 and j=4 , we have |\mathbf{m}_{e_{i}}-\mathbf{m}_{e_{j}}|^{2}\geq\frac{|e_{i}|^{2}+|e_{j}|^{2}}{4}\geq\frac{(|e_{i}|+|e_{j}|)^{2}}{8} , so |\mathbf{m}_{e_{i}}-\mathbf{m}_{e_{j}}|\geq\frac{|e_{i}|+|e_{j}|}{\sqrt{8}} . As a consequence, the balls \B_{1/\sqrt{8}}^{e_{i}} and \B_{1/\sqrt{8}}^{e_{j}} are disjoint. ∎ Proof of Theorem 1.8 . Let k be sufficiently large. For 0\leq i\frac{1}{\sqrt{k}} , or i_{0}=n-1 if there is no such i . On the one hand, for any e\in E_{i_{0}} , the set E_{i_{0}}\setminus\{e\} is a path family of size i_{0}-1 on X , thus S_{2}(E_{i_{0}})-|e|^{2}=S_{2}(E_{i_{0}}\setminus\{e\})\geq S_{2}(E_{i_{0}-1}), i.e., by the definition of i_{0} , |e|^{2}\leq S_{2}(E_{i_{0}})-S_{2}(E_{i_{0}-1})\leq\frac{1}{\sqrt{k}}\quad\text{for any }e\in E_{i_{0}}. (4) On the other hand, for any two endpoints \mathbf{u},\mathbf{v}\in X of different paths in E_{i_{0}} , the set E_{i_{0}}\cup\{\mathbf{u}\mathbf{v}\} is a path family of size i_{0}+1 on X , thus S_{2}(E_{i_{0}})+|\mathbf{u}\mathbf{v}|^{2}=S_{2}(E_{i_{0}}\cup\{\mathbf{u}\mathbf{v}\})\geq S_{2}(E_{i_{0}+1}), so, using the definition of i_{0} again, |\mathbf{u}\mathbf{v}|^{2}\geq S_{2}(E_{i_{0}+1})-S_{2}(E_{i_{0}})>\frac{1}{\sqrt{k}}\quad\text{ for any two endpoints }\mathbf{u},\mathbf{v}\in X\text{ of different paths in }E_{i_{0}}. (5) Set \ell:=\left\lceil\log_{1+\frac{1}{k}}\left(0.9k^{\frac{3}{4}}\right)\right\rceil=O(k\log k),\quad a_{i}:=\frac{\left(1+\frac{1}{k}\right)^{i}}{k^{\frac{3}{4}}} for integers 0\leq i\leq\ell . Note that a_{i}<0.9 for i<\ell , and a_{\ell}\geq 0.9 . Construct a Hamiltonian path P by starting from E_{i_{0}} and successively adding the shortest edge connecting endpoints of two different paths. For 0\leq i\leq\ell , let P_{i}\subseteq P be the path family consisting of all edges e\in P with |e|\leq a_{i}\sqrt{k} . Then P_{0}\subseteq P_{1}\subseteq\dots\subseteq P_{\ell}\subseteq P , and for any two endpoints \mathbf{u},\mathbf{v}\in X of different paths in P_{i} , we have |\mathbf{u}-\mathbf{v}|>a_{i}\sqrt{k} . Due to ( 4 ) and ( 5 ), we have P_{0}=E_{i_{0}} , so P_{0} is S_{2} -minimal among all path families of size i_{0} . Then, by Proposition 5.4 , \mathfrak{B}_{1/\sqrt{8}}^{P_{0}} is a 3-fold packing. It is well-known that the volume V_{k} of the k -dimensional unit ball is V_{k}=\begin{cases}\frac{\pi^{k/2}}{(k/2)!}&\text{if }k\text{ is even},\\ \frac{2^{k}\cdot\pi^{(k-1)/2}((k-1)/2)!}{k!}&\text{if }k\text{ is odd}.\end{cases} By Stirling’s approximation, V_{k}\sim\frac{1}{\sqrt{k\pi}}(\frac{2\pi\mathrm{e}}{k})^{k/2} . Since |e|\leq a_{0}\sqrt{k}=k^{-1/4} for any e\in P_{0} , we have \bigcup_{e\in P_{0}}\B_{1/\sqrt{8}}^{e}\subseteq\left[-k^{-1/4},1+k^{-1/4}\right] , so \sum_{e\in P_{0}}V_{k}\cdot\left(\frac{|e|}{\sqrt{8}}\right)^{k}\leq 3\cdot\left(1+2k^{-1/4}\right)^{k},\quad\text{thus}\quad\sum_{e\in P_{0}}|e|^{k}\leq\frac{3\cdot 8^{k/2}\cdot\left(1+2k^{-1/4}\right)^{k}}{V_{k}}\leq 0.69^{k}\cdot k^{k/2}, for sufficiently large k . Now, for 0\leq i<\ell , let X_{i} be a set containing one endpoint of each path in the path family P_{i} , so |X_{i}|=|X|-|P_{i}| . Then |\mathbf{u}-\mathbf{v}|>a_{i}\sqrt{k} for any distinct \mathbf{u},\mathbf{v}\in X_{i} , and |P_{i+1}\setminus P_{i}|\leq|P|-|P_{i}|=(|X|-1)-(|X|-|X_{i}|)<|X_{i}| . By Lemma 5.2 , we have |X_{i}|\cdot a_{i}^{k}\leq 0.999^{k} . Then \sum_{e\in P_{i+1}\setminus P_{i}}|e|^{k}<|X_{i}|\cdot\left(a_{i+1}\sqrt{k}\right)^{k}=|X_{i}|\cdot\left(a_{i}\sqrt{k}\right)^{k}\cdot\left(1+\frac{1}{k}\right)^{k}\leq\mathrm{e}\cdot 0.999^{k}\cdot k^{k/2}, where \mathrm{e}=2.718.. is Euler’s number. Thus \sum_{e\in P_{\ell}}|e|^{k}=\sum_{e\in P_{0}}|e|^{k}+\sum_{i=1}^{\ell-1}\sum_{e\in P_{i+1}\setminus P_{i}}|e|^{k}<0.69^{k}\cdot k^{k/2}+\mathrm{e}\ell\cdot 0.999^{k}\cdot k^{k/2}=o_{k}(k^{k/2}) for sufficiently large k since \ell=O(k\log k) . Since for any two endpoints \mathbf{u},\mathbf{v} of different paths in P_{\ell} we have |\mathbf{u}-\mathbf{v}|>a_{\ell}\sqrt{k}\geq 0.9\sqrt{k}>\sqrt{\frac{2k}{3}} , by Lemma 5.1 , P_{\ell} consists of at most two paths, i.e. |P\setminus P_{\ell}|\leq 1 , so P is the required Hamiltonian path. ∎ 6 Concluding remarks Theorems 1.7 and 1.9 are non-constructive and do not give a computationally efficient way of finding the Hamiltonian cycle in question. To obtain a constructive result, we can combine these theorems with an approximation algorithm. A complete graph on a vertex set X with edge weights w(a,b) , a,b\in X , satisfies the \tau -relaxed triangle inequality for \tau\geq 1 if w(a,c)\leq\tau\cdot(w(a,b)+w(b,c)) for all a,b,c\in X . Bender and Chekuri [ 3 , Theorem 1] gave a polynomial-time 4\tau -approximation algorithm for the travelling salesman problem in graphs satisfying the \tau -relaxed triangle inequality. By Hölder’s inequality, for any \mathbf{a},\mathbf{b},\mathbf{c}\in{\mathbb{R}}^{k} we have |\mathbf{a}-\mathbf{c}|^{k}\leq\left(|\mathbf{a}-\mathbf{b}|+|\mathbf{a}-\mathbf{c}|\right)^{k}\leq\left(1^{\frac{k}{k-1}}+1^{\frac{k}{k-1}}\right)^{k-1}\left(|\mathbf{a}-\mathbf{b}|^{k}+|\mathbf{b}-\mathbf{c}|^{k}\right)=2^{k-1}\left(|\mathbf{a}-\mathbf{b}|^{k}+|\mathbf{b}-\mathbf{c}|^{k}\right). In other words, for a finite set X\subseteq{\mathbb{R}}^{k} , the complete graph K(X) with edge weights w(\mathbf{a},\mathbf{b}):=|\mathbf{a}-\mathbf{b}|^{k} , \mathbf{a},\mathbf{b}\in X , satisfies the 2^{k-1} -relaxed triangle inequality, which implies the following corollary. Corollary 6.1 . For any X\subseteq[0,1]^{k} , |X|=n , one can construct a Hamiltonian cycle H on X in time polynomial in n such that S_{k}(H)\leq 2^{k+2}\cdot\mathrm{e}(k+1)\cdot k^{k/2} , or S_{k}(H)\leq 2^{k+2}\cdot k^{k/2}\cdot(1+o_{k}(1)) . In the conclusion of their paper [ 2 ] , Balogh, Clemen and Dumitrescu proposed a variant of the problem with a different condition in place of X\subseteq[0,1]^{k} : they asked to determine the extremal value of S_{k}^{\mathrm{HC}}(X) over all finite sets X\subseteq{\mathbb{R}}^{k} with \diam X\leq 1 . They noted that the set of k+1 vertices X_{k} of the unit simplex in {\mathbb{R}}^{k} satisfies \diam X_{k}=1 and S_{k}^{\mathrm{HC}}(X_{k})=k+1 , and asked if this is optimal. With present tools, we can prove the following upper bound. Theorem 6.2 . For any finite set X\subseteq{\mathbb{R}}^{k} with \diam X\leq 1 , there exists a Hamiltonian cycle H on X with S_{k}(H)\leq 2\mathrm{e}\left(\frac{2k}{k+1}\right)^{k/2}\cdot(k+1)\leq 2\mathrm{e}\cdot 2^{k/2}\cdot(k+1), where \mathrm{e}=2.718.. is Euler’s number. Proof. According to Jung’s theorem [ 8 ] (see [ 7 , Theorem 3.3] for a more contemporary treatment), there exists a closed ball of radius r:=\sqrt{\frac{k}{2(k+1)}} that contains X . Then, after a parallel translation, we may assume that |\mathbf{a}|\leq r for any \mathbf{a}\in X . Let H be a Hamiltonian cycle on X which minimizes S_{2}(H) , and let \alpha=\sqrt{\frac{t}{4(t+1)}} , where t is given by Lemma 4.4 , thus \frac{2t+1}{\alpha^{k}}\leq(k+1)\mathrm{e}\cdot 2^{k}. By Proposition 4.3 , \mathfrak{B}_{\alpha}^{H} is a (2t+1) -fold packing, then so is \mathfrak{hB}_{\alpha}^{H} . Due to Lemma 2.2 , \hB_{\alpha}^{e}\subseteq\B_{r}(\mathbf{0}) for each edge e\in H . Denoting by V_{k} the volume of the k -dimensional unit ball, we have \sum_{e\in H}\frac{V_{k}}{2}\alpha^{k}|e|^{k}\leq(2t+1)\cdot V_{k}r^{k},\quad\text{so}\quad S_{k}(H)\leq 2\cdot\frac{2t+1}{\alpha^{k}}\cdot r^{k}\leq 2\mathrm{e}(k+1)\cdot\left(\frac{2k}{k+1}\right)^{k/2}.\qed Email address: gordeev.aleksei@renyi.hu Department of Mathematics and Mathematical Statistics, Umeå University, Universitetstorget 4, 901 87 Umeå, Sweden; HUN-REN Alfréd Rényi Institute of Mathematics, Reáltanoda utca 13–15., H-1053 Budapest, Hungary; MTA–HUN-REN RI Lendület ‘‘Momentum’’ Arithmetic Combinatorics Research Group, Reáltanoda utca 13–15., H-1053 Budapest, Hungary. Appendix A Alternative exact upper bounds In this section, we prove an exact upper bound on S_{k}^{\mathrm{HC}} using properties of spherical codes, i.e. Lemma 3.3 , and an exact upper bound on S_{k}^{\mathrm{PM}} using properties of centroids, i.e. Lemma 4.2 . The resulting Theorems A.2 and A.4 are slightly weaker than, respectively, Theorems 1.9 and 1.11 . Proposition A.1 . Let X\subseteq{\mathbb{R}}^{k} be a finite set, and let H be a Hamiltonian cycle on X with minimal possible S_{2}(H) . Then \mathfrak{B}_{1/2}^{H} is a 3(k+1) -fold packing. Proof. Fix any point \mathbf{x}\in{\mathbb{R}}^{k} and let it be contained in the ball \B_{1/2}^{e_{i}} for n distinct edges appearing in the cycle in the order e_{1},\dots,e_{n}\in H . Denoting \mathbf{m}_{i}:=\mathbf{m}_{e_{i}} , we have |\mathbf{m}_{i}-\mathbf{x}|^{2}<|e_{i}|^{2}/4 for 1\leq i\leq n . By Lemma 4.1 , for any 1\leq i_{1}|\mathbf{m}_{i_{1}}-\mathbf{x}|^{2}+|\mathbf{m}_{i_{2}}-\mathbf{x}|^{2}+|\mathbf{m}_{i_{3}}-\mathbf{x}|^{2}+|\mathbf{m}_{i_{4}}-\mathbf{x}|^{2}. Thus, either |\mathbf{m}_{i_{1}}-\mathbf{m}_{i_{3}}|^{2}>|\mathbf{m}_{i_{1}}-\mathbf{x}|^{2}+|\mathbf{m}_{i_{3}}-\mathbf{x}|^{2} , and so \langle\mathbf{m}_{i_{1}}-\mathbf{x},\mathbf{m}_{i_{3}}-\mathbf{x}\rangle=\frac{|\mathbf{m}_{i_{1}}-\mathbf{x}|^{2}+|\mathbf{m}_{i_{3}}-\mathbf{x}|^{2}-|(\mathbf{m}_{i_{1}}-\mathbf{x})-(\mathbf{m}_{i_{3}}-\mathbf{x})|^{2}}{2}<0, or, similarly, \langle\mathbf{m}_{i_{2}}-\mathbf{x},\mathbf{m}_{i_{4}}-\mathbf{x}\rangle<0 . Consider an auxiliary graph G with the vertex set \{1,\dots,n\} and an edge between i\neq j whenever \langle\mathbf{m}_{i}-\mathbf{x},\mathbf{m}_{j}-\mathbf{x}\rangle\geq 0 . Draw this graph on the plane, placing vertices at the corners of a regular n -sided polygon, and drawing edges of G as segments. We have shown that for any i_{1}