For a graph whose vertices are points in $\mathbb R^d$, consider the closed balls with diameters induced by its edges. The graph is called a Tverberg graph if these closed balls intersect. A max-sum tree of a finite point set $X \subset \mathbb R^d$ is a tree with vertex set $X$ that maximizes the sum of Euclidean distances of its edges among all trees with vertex set $X$. Similarly, a max-sum matching of an even set $X \subset \mathbb R^d$ is a perfect matching of $X$ maximizing the sum of Euclidean distances between the matched points among all perfect matchings of $X$. We prove that a max-sum tree of any finite point set in $\mathbb R^d$ is a Tverberg graph, which generalizes a recent result of Abu-Affash et al., who established this claim in the plane. Additionally, we provide a new proof of a theorem by Bereg et al., which states that a max-sum matching of any even point set in the plane is a Tverberg graph. Moreover, we proved a slightly stronger version of this theorem.
翻译:对于一张其顶点位于 $\mathbb R^d$ 中的点的图,考虑其边所诱导的直径为相应边权的闭球体。若这些闭球体相交,我们称该图为 Tverberg 图。给定一个有限点集 $X \subset \mathbb R^d$,其 max-sum 树是一棵顶点集为 $X$ 并使得其边的欧几里德距离和最大的树。同样地,对于任意偶数点集 $X \subset \mathbb R^d$,其 max-sum 匹配是一个 $X$ 的完美匹配,使得其匹配点之间的欧几里德距离和最大。我们证明了任意有限点集的 max-sum 树都是 Tverberg 图,从而推广了近期 Abu-Affash 等人在平面上证明的结论。此外,我们对 Bereg 等人的定理进行了新的证明,该定理指出平面上任意偶数点集的 max-sum 匹配都是 Tverberg 图。此外,我们还证明了该定理的一个略微更强的版本。