Diametral Balls of Max-Sum Matchings: Counterexamples and Dimension-Independent Bounds

For an even set of points in Euclidean space, a max-sum matching is a perfect matching of maximum total length. Bereg et al. proved that the closed disks having the edges of a max-sum matching of a planar set as diameters always have a common point, and Barabanshchikova and Polyanskii proved that the open disks have one when the points are distinct. Whether the same holds in higher dimensions was asked by Pirahmad, Polyanskii and Vasilevskii and by Barabanshchikova and Polyanskii, and it is Open Problem 14 in Polyanskii's survey of no-dimensional Tverberg problems. We give six distinct points of ℤ³, with coordinates at most 150 in absolute value, whose max-sum matching is unique and whose three closed diametral balls have no common point. Hence the answer is negative in every dimension d ≥ 3, and the conjecture of Barabanshchikova and Polyanskii that the intersection contains a ball of radius proportional to the minimum distance of the set fails for every d ≥ 3. Six is the smallest possible number of points, because any two diametral balls of a max-sum matching intersect. A known Jung-type lemma for balls of different radii then shows that the diametral balls of a max-sum matching in ℝᵈ have a common point once each is enlarged about its centre by the factor √(2d/(d + 1)), and we show that in ℝ³ the factor 1.0095 is not enough. Using both ways of exchanging the partners of two edges, we show that the factor √((3 + √17)/4) ≈ 1.3345 suffices in every dimension, and √(5/3) suffices when all edges have the same length. As a consequence, every perfect matching that cannot be lengthened by exchanging the partners of two edges has at least 0.5996 times the maximum total length, in every dimension.