ИСТИНА

We will discuss how the Gromov-Hausdorff distance arises in various combinatorial and geometric optimization problems. First, we recall our results (obtained jointly with Professor Alexander O. Ivanov) on (1) Borsuk’s problem about the smallest number of parts into which a bounded subset of Euclidean space can be cut so that all parts have a smaller diameter than the original subset; (2) finding the smallest number of colors necessary to correctly color the vertices of the graph; (3) calculating the smallest number of cliques whose vertices cover the set of vertices of the graph; (4) calculating the weights of the edges of the minimum spanning tree in the weighted graph. After this, we will show how to express through the Gromov- Hausdorff distance the l1-dimension, i.e., the smallest dimension of a vector space with Manhattan (l1−) norm into which a given finite metric space can be isometrically embedded.