Embeddings to Rectilinear Space and Gromov–Hausdorff Distances
A. O. Ivanov, A. A. Tuzhilin · 2024
Read Embeddings to Rectilinear Space and Gromov–Hausdorff Distances by A. O. Ivanov, A. A. Tuzhilin (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-19202.txt.
Introduction
Ivanov and Tuzhilin study embeddings into rectilinear space in two thousand twenty-four. Rectilinear space measures distance by the sum of gaps along each axis. They ask when a given finite metric space can be placed inside such a space of set dimension. Their result restates that question in a new form. The test becomes a Gromov-Hausdorff distance between certain special finite metric spaces. That distance gauges how close two spaces sit in shape. The paper is a brief note with a single sharp claim.
Catalog record
| CREATOR | A. O. Ivanov, A. A. Tuzhilin |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 35 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-19202
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Embeddings to Rectilinear Space and Gromov–Hausdorff Distances A. O. Ivanov, A. A. Tuzhilin Abstract We show that the problem whether a given finite metric space can be embedded into m m -dimensional rectilinear space can be reformulated in terms of the Gromov–Hausdorff distance between some special finite metric spaces. MSC 2020: 46B85, 51F99, 53C23. Keywords: Gromov–Hausdorff distance, Rectilinear space, Isometric embeddings, Finite metric spaces, normed spaces 1 Introduction We continue our investigations [ 39 ] , [ 25 ] , [ 27 ] , [ 28 ] on connections between the geometry of Gromov–Hausdorff distance and Discrete Geometry problems such as calculation of edges weights of a minimal spanning tree, Borsuk conjecture, chromatic number and clique cover number calculation for a simple graph, etc. In this paper we give an answer to a question whether a given finite metric space (X,d) can be embedded into m -dimensional rectilinear space in terms of the Gromov–Hausdorff distance. Hyperspaces For subsets A and B of a fixed metric space X , a natural distance function d_{H} was defined by F. Hausdorff [ 18 ] as the infimum of positive numbers r such that A is contained in the r -neighborhood of B , and vice-versa. It is well-known that this function, referred as the Hausdorff distance , is a metric on the family of all closed bounded subsets of the metric space X , see for example [ 9 ] . The Hausdorff distance was generalized to the case of two metric spaces X and Y by D. Edwards [ 13 ] and independently by M. Gromov [ 15 ] . The Gromov–Hausdorff distance between the spaces X and Y equals the infimum of the values d_{H}\big(\varphi(X),\psi(Y)\big) over all possible isometrical embeddings \varphi\colon X\to Z and \psi\colon Y\to Z into all possible metric spaces Z . It is well-known that this distance function is a metric on the family of isometry classes of non-empty compact metric spaces. The corresponding hyperspace is usually denoted by {\cal M} and is referred as the Gromov–Hausdorff space (see [ 9 ] ). The geometry of the Gromov–Hausdorff space is rather tricky and is intensively investigated by many authors, see, for example, a review in [ 9 ] . The technique of optimal correspondences permitted to prove that the space {\cal M} is geodesic [ 22 , 11 , 20 ] and to describe some local and all global isometries of {\cal M} , see [ 21 , 24 ] . Since finite metric spaces form an everywhere dense subset of {\cal M} , the distances to such spaces and between such spaces play an important role in the research of geometry of {\cal M} . Important classes of such spaces are formed by the ones all whose non-zero distances are the same (so-called single-distance spaces or simplexes ) and by the spaces whose non-zero distances take only two different values (so-called two-distance spaces ). The authors, together with S. Iliadis and D. Grigor’ev, see [ 19 ] , [ 14 ] , calculated distances from a bounded metric space to a simplex, and, as a particular case, the distances between any simplex and any 2 -distance space, see [ 26 ] . It turns out that the Gromov–Hausdorff distance from a metric space X to a simplex “feels” somehow a geometry of partitions of the space X . The latter explains some relations between the Gromov–Hausdorff distance and Discrete Geometry Problems. Discrete Geometry Problems In 1933, K. Borsuk stated the following question: How many parts one needs to partition an arbitrary subset of the Euclidean space into, to obtain pieces of smaller diameters? He made the following famous conjecture: Any bounded non-single-point subset of \mathbb{R}^{n} can be partitioned into at most n+1 subsets, each of which has smaller diameter than the initial subset. K. Borsuk himself proved it for n=2 and for a ball in 3 -dimensional space, [ 4 ] and [ 5 ] . For n=3 the conjecture was proved by J. Perkal (1947) and by H. G. Eggleston (1955), then for convex subsets with smooth boundaries in 1946 by H. Hadwiger [ 16 , 17 ] , and for central symmetric bodies by A. S. Riesling (1971). However, in 1993 the conjecture was disproved in general case by J. Kahn, and G. Kalai, see [ 31 ] . They constructed a counterexample in dimension n=1325 , and also proved that the conjecture is not valid for all n>2014 . This estimate was consistently improved by Raigorodskii, n\geq 561 , Hinrichs and Richter, n\geq 298 , Bondarenko, n\geq 65 , and Jenrich, n\geq 64 , see details in a review [ 37 ] . Notice that all the examples are finite subsets of the corresponding spaces, and the best known results of Bondarenko [ 7 ] and Jenrich [ 30 ] are the 2 -distance subsets of the unit sphere. On the other hand, Lusternik and Schnirelmann [ 34 ] , and a bit later independently Borsuk [ 4 ] and [ 5 ] , see also [ 42 ] , have shown that the standard sphere and the standard ball in \mathbb{R}^{n} , n\geq 2 , cannot be partitioned into m\leq n subsets having smaller diameters. Thus, the least possible number of parts of smaller diameter, necessary to partition the sphere and the ball in \mathbb{R}^{n} equals n+1 . In paper [ 27 ] we stated a generalized Borsuk problem, passing to an arbitrary bounded metric space X and its partitions of an arbitrary cardinality m (not necessary finite), and gave a criterion solving the Borsuk problem in terms of the Gromov–Hausdorff distance. Namely, it is shown that to verify the existence of an m -partition into subsets of smaller diameter, it suffices to calculate the Gromov–Hausdorff distance from the space X to a simplex having the cardinality m and a smaller diameter than X . As a corollary, a solution to the Borsuk problem for a 2 -distance space X with distances a<b is obtained in terms of the clique cover number of the simple graph G with vertex set X , whose vertices x and y are connected by an edge iff |xy|=a . Recall that a clique cover of a given simple graph is a cover of the vertex set of the graph by subsets such that every their two vertices are adjacent. Each such subset is called a clique and is a vertex set of a complete subgraph that is also referred as a clique . The minimum k for which a k -element clique cover exists is called the clique cover number of the given graph. Further, a graph coloring is an assignment of labels (that are traditionally called “colors”) to vertices of a graph in such a way that no two adjacent vertices are of the same color. The smallest number of colors necessary to color a graph is called its chromatic number . It is not difficult to see that the clique cover can be considered as a graph coloring of the complement graph, hence the clique cover number of a graph equals to the chromatic number of the complement one. Calculation and estimation of these numbers