The Travelling Polytope Constant of a Product of Trees: An Answer to a Question of Genevois

Abstract

The travelling polytope constant TP(X) of a graph X compares the travelling salesman problem through a finite set F of vertices with the shortest way to sweep F by convex hulls which grow or shrink by one adjacent vertex at a time. A. Genevois introduced it in his thesis (2017), as the travelling salesman constant of a CAT(0) cube complex; he proved that it equals d/(2d − 1) for ℤ^d and lies in [1/2, 2/3] ∪ {1} for unbounded median graphs of bounded degree, and asked for its value for a product of two trees. At the Oberwolfach workshop Median Geometry and Applications (2026) he asked again to compute it for products of (regular) trees. We show that TP(T₁ × ⋯ × T_d) = d′/(2d′ − 1), where d′ ≥ 1 is the number of factors of unbounded diameter, without any assumption on the degrees, and treat the remaining cases, in which all factors have finite diameter. So a product of d regular trees of degree at least 2 has constant d/(2d − 1), as Genevois's guess for cocompact cube complexes predicts. The upper bound is Genevois's grid example for ℤ^d, placed on geodesic segments of the factors. The new part is the lower bound: by Genevois's formula, the shortest sweep has twice as many steps as there are hyperplanes separating two of the points, and Euler tours of the projected hulls give a 1-Lipschitz map from a box onto the hull of the points, through which the classical strip bound for the travelling salesman problem in a cube applies. The values obtained were known values of the constant, so the note gives no new value; which values the constant takes on median graphs remains open. This is an unrefereed note. Unrefereed preprint released for independent mathematical scrutiny. Publication on Zenodo does not constitute peer review. AI-assisted tools supported research, computation, proof development, and manuscript preparation. The author remains responsible for all claims and the final text. Corpus identifier: OWR-14299911-020 (Oberwolfach Reports, Report 8/2026, Problem 7, "Travelling polytopes").