On Tue, Jan 5, 2021 at 2:46 PM Dan Asimov <asimov@msri.org> wrote:
Let T^2 = R^2/Z^2 denote the square torus, i.e., a unit square with its opposite edges identified.
Let X = {x_1, ..., x_n} be any set of n distinct points of T^2 where n = 2k is even.
Puzzle: ------- Does there necessarily exist n/2 disjoint line segments in T^2 whose n endpoints form the entire set X ??? Proof or counterexample.
Yes. In fact, this is true of 2n points in the square, without the additional possibilities given by identifying the edges. If all the points have different y coordinates, just sort by y, and draw segments between the top 2, the next 2, etc. If some points have the same y coordinate, choose a small e such that all points have different values of z = y + e x, and sort by z instead of y.
(Note that on T^2 there are infinitely many line segments between points p and q.)
Question: --------- When X is such that there does exist such a collection of n/2 disjoint line segments, can they always be chosen so as to be *shortest* line segments???
At first I thought the same construction still worked. I think it still does, but with a slight modification . Suppose we try choosing the same pairs of points, but use the shortest segment between the two points. This works if the shortest segment stays in the square, or if it "wraps around in the x direction", that is, using the identification of (0,y) with (1, y). But it can fail if the shortest segment wraps in the y direction. using the identification of (x, 0) and (x, 1). But this can only happen if the y-coordinates of the 2 points differ by >= 1/2. In this case, use the same pairing technique, but start just below this large gap in y-coordinates. That is, if the points include 2 points (x_1, y_1) and (x_2, y_2) with y_1 - y_2 >= 1/2, and with no other point (x_i, y_i) with y_2 <= y_i <= y_1 (note that this can happen for at most one pair of values y_1 and y_2), then sort by y as before, but sorting with all values of y <= y_2 counting as "greater" than all values of y >= y_1 (and using normal comparisons of y-coordinates in comparing two points that are either both above or both below the gap). Harder question; is this true on an arbitrary Riemanian manifold? There can sometimes be infinitely many "shortest paths" between two points, (such as connecting the poles of a sphere, but we just require that the path drawn be any one of the shortest geodesics connecting the pair of points. Andy
(If points p and q of T^2 are less than the maximum possible distance of √(1/2) apart, then there is a unique shortest segment connecting them. If their distance is √(1/2) then there are four such segments.)
—Dan _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com