Geodesic
Gromov--Hausdorff distances to simplexes and some applications to discrete optimisation
Čebyševskij sbornik, Tome 21 (2020) no. 2, pp. 169-189.

Voir la notice de l'article provenant de la source Math-Net.Ru

Relations between Gromov–Hausdorff distance and Discrete Optimisation problems are discussed. We use the Gromov–Hausdorff distances to single-distance metric space for solving the following problems: calculation of lengths of minimum spanning tree edges of a finite metric space; generalised Borsuk problem; chromatic number and clique cover number of a simple graph calculation problems.
Keywords: Gromov–Hausdorff distance, minimum spanning tree, Borsuk problem, chromatic number, clique covering, metric geometry, discrete optimisation. 
@article{CHEB_2020_21_2_a13,
     author = {A. O. Ivanov and A. A. Tuzhilin},
     title = {Gromov--Hausdorff distances to simplexes and some applications to discrete optimisation},
     journal = {\v{C}eby\v{s}evskij sbornik},
     pages = {169--189},
     publisher = {mathdoc},
     volume = {21},
     number = {2},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CHEB_2020_21_2_a13/}
}
TY  - JOUR
AU  - A. O. Ivanov
AU  - A. A. Tuzhilin
TI  - Gromov--Hausdorff distances to simplexes and some applications to discrete optimisation
JO  - Čebyševskij sbornik
PY  - 2020
SP  - 169
EP  - 189
VL  - 21
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/CHEB_2020_21_2_a13/
LA  - en
ID  - CHEB_2020_21_2_a13
ER  - 
%0 Journal Article
%A A. O. Ivanov
%A A. A. Tuzhilin
%T Gromov--Hausdorff distances to simplexes and some applications to discrete optimisation
%J Čebyševskij sbornik
%D 2020
%P 169-189
%V 21
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/CHEB_2020_21_2_a13/
%G en
%F CHEB_2020_21_2_a13
A. O. Ivanov; A. A. Tuzhilin. Gromov--Hausdorff distances to simplexes and some applications to discrete optimisation. Čebyševskij sbornik, Tome 21 (2020) no. 2, pp. 169-189. http://geodesic.mathdoc.fr/item/CHEB_2020_21_2_a13/

[1] Deza M. M., Deza E., Enciclopedia of Distances, Springer Verlag, Berlin–Heidelberg, 2014 | MR

[2] A. Illanes, S. Nadler, Hyperspaces. Fundamentals and Recent Advances, Marcel Dekker Inc., New York–Basel, 1999 | MR | Zbl

[3] D. Burago, Yu. Burago, S. Ivanov, A Course in Metric Geometry, Graduate Studies in Mathematics, 33, A.M.S., Providence, RI, 2001 | DOI | MR | Zbl

[4] F. Hausdorff, Grundzüge der Mengenlehre, Veit, Leipzig, 1914 ; reprinted Chelsea, 1949 | MR | Zbl

[5] D. Edwards, The Structure of Superspace, Studies in Topology, Academic Press, 1975 | MR

[6] M. Gromov, Groups of Polynomial growth and Expanding Maps, Publications Mathematiques I.H.E.S., 53, 1981 ; 2015, arXiv: 1504.03830 | MR | Zbl

[7] Ivanov A. O., Nikolaeva N. K., Tuzhilin A. A., “The Gromov–Hausdorff Metric on the Space of Compact Metric Spaces is Strictly Intrinsic”, Mathematical Notes, 100:6 (2016), 171–173 | MR | Zbl

[8] S. Iliadis, A. Ivanov, A. Tuzhilin, “Local Structure of Gromov–Hausdorff Space, and Isometric Embeddings of Finite Metric Spaces into this Space”, Topology and its Applications, 221 (2017), 393–398 ; (2016), arXiv: ; (2016), arXiv: 1604.076151611.04484 | DOI | MR | Zbl

[9] A. O. Ivanov, A. A. Tuzhilin, “Isometry group of Gromov–Hausdorff Space”, Matematicki Vesnik, 71:1–2 (2019), 123–154 | MR

[10] A. O. Ivanov, S. D. Iliadis, A. A. Tuzhilin, Geometry of Compact Metric Space in Terms of Gromov-Hausdorff Distances to Regular Simplexes, 2016, arXiv: 1607.06655 | MR

[11] Grigor'ev D. S., Ivanov A. O., Tuzhilin A. A., “Gromov–Hausdorff Distance to Simplexes”, Chebyshev. Sbornik, 20:2 (2019), 108–122 | MR | Zbl

[12] A. O. Ivanov, A. A. Tuzhilin, The Gromov–Hausdorff Distance Between Simplexes and Two-Distance Spaces, 2019, arXiv: 1907.09942 | MR

[13] J. B. Kruskal, “On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem”, Proceedings of the American Mathematical Society, 7 (1956), 48–50 | DOI | MR | Zbl

[14] K. Borsuk, “Über die Zerlegung einer $n$-dimensionalen Vollkugel in $n$-Mengen”, Verh. International Math. Kongress Zürich, 1932, 192 pp.

[15] K. Borsuk, “Drei Sätze über die $n$-dimensionale euklidische Sphäre”, Fundamenta Math., 20 (1933), 177–190 | DOI

[16] Lusternik L. A., Schnirelmann L. G., Topological Methods in Variational Problems, Issled. Inst. Matem. i Mekh. pri MGU, M., 1930 (in Russian)

[17] G. M. Ziegler, “Colouring Hamming Graphs, Optimal Binary Codes, and the $0/1$-Borsuk Problem in Low Dimensions”, Computational Discrete Mathematics, ed. H. Alt, Springer-Verlag, Berlin–Heidelberg–New York, 2001, 159–172 | DOI | MR

[18] H. Hadwiger, “Überdeckung einer Menge durch Mengen kleineren Durchmessers”, Commentarii Mathematici Helvetici, 18:1 (1945), 73–75 | DOI | MR | Zbl

[19] H. Hadwiger, “Mitteilung betreffend meine Note: Überdeckung einer Menge durch Mengen kleineren Durchmessers”, Commentarii Mathematici Helvetici, 19 (1946) | MR | Zbl

[20] J. Kahn, G. Kalai, “A counterexample to Borsuk's conjecture”, Bull. Amer. Math. Soc., 29:1 (1993), 60–62 | DOI | MR | Zbl

[21] A. M. Raigorodskii, “Around Borsuk's Hypothesis”, Journal of Mathematical Sciences, 154:4 (2008), 604–623 | DOI | MR | Zbl

[22] A. V. Bondarenko, On Borsuk's conjecture for two-distance sets, 2013, arXiv: 1305.2584 | MR

[23] T. Jenrich, A $64$-dimensional two-distance counterexample to Borsuk's conjecture, 2013, arXiv: 1308.0206 | MR

[24] R. M. R. Lewis, A Guide to Graph Colouring, Springer, Cham, 2016 | MR | Zbl

[25] A. A. Tuzhilin, Calculation of Minimum Spanning Tree Edges Lengths using Gromov–Hausdorff Distance, 2016, arXiv: 1605.01566

[26] Ivanov A. O., Nikonov I. M., Tuzhilin A. A., “Sets Admitting Connection by Graphs of Finite Length”, Sbornik: Mathematics, 196:6 (2005), 845–884 | DOI | MR | Zbl