China-Russia Mathematics Center logoPKU School 2026

Course Program

Alexey A. Tuzhilin

Gromov–Hausdorff distance: applications and lower bounds

Alexey A. Tuzhilin

Lomonosov Moscow State University

This four-lecture series studies applications of GH distance, lower bounds, ultrametrization, topological methods, and finite-dimensional normed-space techniques.

Lecture 1

Applications of GH distance: MST-spectrum, Borsuk problem and combinatorial invariants

Lecture 2

Ultrametrization and its applications in GH geometry

Lecture 3

Topological methods in GH-distance estimates

Lecture 4

Estimation of the GH-distance to a normed space through the Jung constant

Detailed contents

Lecture outlines

Lecture 1

Applications of GH distance: MST-spectrum, Borsuk problem and combinatorial invariants

  1. The MST-spectrum and GH-distances to simplices

    The MST-spectrum through partitions of a metric space, and a formula for the MST-spectrum in terms of the GH-distance to simplices.

  2. The generalized Borsuk problem

    A criterion for the existence of a Borsuk partition in terms of the GH-distance to a simplex.

  3. Chromatic number, clique cover number and Manhattan dimension via GH distances

    Formulas expressing the chromatic number, the clique cover number and the Manhattan dimension through GH-distances to a simplex.

  4. Auxiliary constructions

    A cut, a hypergraph, the nested hypergraph Γ(C), and the family of simple graphs G(C).

Accepted as a known fact. Invariance of the MST-spectrum (Grigor'ev, Ivanov, Tuzhilin, 2019); duality of the clique cover number and the chromatic number; the Assouad criterion (Assouad, Deza, 1982); the Bandelt–Chepoi–Laurent theorem (Bandelt, Chepoi, Laurent, 1998).

Lecture 2

Ultrametrization and its applications in GH geometry

  1. Ultrametric spaces

    The strong triangle (polygon) inequality and the basic properties of ultrametric spaces, with examples.

  2. Ultrametrization

    The ultrametrization U(X) as the maximal ultrametric below a given metric, and its properties.

  3. Main theorem on ultrametrization

    Ultrametrization does not increase GH-distances: dGH(X, Y) ≥ dGH(U(X), U(Y)).

  4. Applications to computing GH distances

    The exact GH-distances between a circle and a regular polygon, and between two regular polygons.

  5. The circumscribed ball radius and the Jung constant

    The circumscribed ball radius and the Jung constant of a normed space, and the relation between ultrametrization and the Jung constant.

  6. Relation to the MST-spectrum

    The diameter of U(X) equals the largest element of the MST-spectrum.

Accepted as a known fact. The theory of ultrametric spaces and their representation through trees (Ivanov, Tuzhilin); results on the GH-distance between simplices (Grigor'ev, Ivanov, Tuzhilin, 2019). Left outside the scope of the minicourse: generalization to infinite spaces and to p-ultrametrization.

Lecture 3

Topological methods in GH-distance estimates

  1. Simplicial complexes and their homology

    Simplicial complexes and their geometric realization, orientations of simplices, chain groups, the boundary operator and homology groups.

  2. The Čech and Vietoris–Rips complexes

    Definitions of the Čech complex and of the Vietoris–Rips complex of a metric space.

  3. Relation between the Čech and Vietoris–Rips complexes

    Inclusions VR(X, r) ⊂ Čr(X) putting the Vietoris–Rips complex inside the Čech complex.

  4. Proximity of Vietoris–Rips complexes

    For spaces that are close in the GH sense, their Vietoris–Rips complexes are close (nearly homotopy equivalent).

  5. The Jung constant and the relation between the complexes

    The Vietoris–Rips complex maps into the Čech complex scaled by the Jung constant J(Z).

  6. Higher homology of connected manifolds

    For a connected closed n-manifold the top homology of every proper open subset vanishes.

Accepted as a known fact. Homotopy invariance of homology (Hatcher, 2002); the nerve lemma of Leray (Hatcher, 2002); paracompactness of metric spaces (Stone, 1948); closeness of simplicial mappings (Adams, Frick, Majhi, McBride, 2026); higher homology of connected manifolds (Hatcher, 2002).

Lecture 4

Estimation of the GH-distance to a normed space through the Jung constant

  1. Problem statement and basic definitions

    Estimating the GH-distance from a finite-dimensional normed space V to a subset X, and the basic definitions involved.

  2. Radii, the Jung constant and the Gulevich number

    The circumscribed ball radius R(A), the relative radius RY(A), the Jung constant J(V), the relative Jung constant Js(V), the measure of nonconvexity λ(A) and the Gulevich number G(V).

  3. Weak estimate of the GH-distance

    The weak estimate dGH(V, X) ≥ dH(V, X)/(2Js(V)), proved via the triangulation and continuous-extension lemmas.

  4. The intersection property

    The intersection property of a normed space (definition) and its consequences.

  5. The strengthened estimate

    The strengthened estimate dGH(V, X) ≥ dH(V, X)/(2J(V)) for spaces with the intersection property.

  6. Corollaries: equality for the sup-norm

    For the sup-norm (and for cylindrical norms, or dim V = 2) the estimate becomes the exact equality dGH(V, X) = dH(V, X).

Accepted as a known fact. Gulevich's theorem that the Gulevich number coincides with the relative Jung constant for Banach spaces (Adams et al., 2026); values of the Jung constant for Euclidean spaces and the sup-norm (Jung, 1901; Berdyshev, 1998; Amir, 1985); the criterion J(V) = Js(V) (Klee, 1960; Garkavi, 1964); the intersection property for Euclidean spaces, the sup-norm and cylindrical norms, and the existence of norms without it (Adams et al., 2026); Webster's lemma (Bourgin, 1975).

Reading list

References for the lecture series

Works cited across the lectures of this minicourse.

  1. H. Adams, S. A. Bogatyi, F. Frick, D. A. Ilyukhin, A. O. Ivanov, I. N. Mikhailov, A. A. Tuzhilin, A. A. Vikhrov. Gromov-Hausdorff distance and Jung constant of finite-dimensional normed spaces. arXiv:2607.18447, 2026.
  2. H. Adams, F. Frick, S. Majhi, N. McBride. Hausdorff vs Gromov-Hausdorff Distances. Discrete & Computational Geometry, vol. 75, pp. 1217–1246, 2026. arXiv:2309.16648. DOI:10.1007/s00454-025-00722-9.
  3. D. Amir. On Jung's constant and related constants in normed linear spaces. Pacific Journal of Mathematics, vol. 118, no. 1-15, pp. 359–371, 1985. DOI:10.2140/pjm.1985.118.1.
  4. P. Assouad, M. Deza. Metric Subspaces of L1. Publications mathématiques d'Orsay, 82-03, Université de Paris Sud, Orsay, 1982.
  5. H.-J. Bandelt, V. Chepoi, M. Laurent. Embedding into Rectilinear Spaces. Discrete & Computational Geometry, vol. 19, no. 4, pp. 595–604, 1998. DOI:10.1007/PL00009370.
  6. S. V. Berdyshev. The relative Jung constant in the space ln∞. Trudy Instituta Matematiki i Mekhaniki (Ekaterinburg), vol. 5, pp. 97–103, 1998. (In Russian).
  7. A. I. Bikeev, A. M. Raigorodskii. On upper bounds on the number of parts in the problem of partitioning sets into parts of smaller diameter. arXiv:2508.14578, 2025.
  8. A. V. Bondarenko. On Borsuk's conjecture for two-distance sets. Discrete & Computational Geometry, vol. 51, no. 3, pp. 509–515, 2014. arXiv:1305.2584. DOI:10.1007/s00454-014-9579-4.
  9. K. Borsuk. Drei Sätze über die n-dimensionale euklidische Sphäre. Fundamenta Mathematicae, vol. 20, pp. 177–190, 1933. DOI:10.4064/fm-20-1-177-190.
  10. R. D. Bourgin. Approximate isometries on finite dimensional Banach spaces. Transactions of the American Mathematical Society, vol. 207, pp. 309–328, 1975. DOI:10.1090/S0002-9947-1975-0370137-4.
  11. G. Carlsson, F. Mémoli. Characterization, stability and convergence of hierarchical clustering methods. Journal of Machine Learning Research, vol. 11, pp. 1425–1470, 2010. jmlr.org.
  12. F. Chazal, V. de Silva, M. Glisse, S. Oudot. The Structure and Stability of Persistence Modules. SpringerBriefs in Mathematics, Springer, 2013. arXiv:1207.3674.
  13. A. L. Garkavi. On the Chebyshev center and convex hull of a set. Uspekhi Matematicheskikh Nauk, vol. 19, no. 6(120), pp. 139–145, 1964. (In Russian). Math-Net.Ru.
  14. J. C. Gower, G. J. S. Ross. Minimum spanning trees and single linkage cluster analysis. Journal of the Royal Statistical Society. Series C (Applied Statistics), vol. 18, no. 1, pp. 54–64, 1969. DOI:10.2307/2346439. jstor.org.
  15. J. Grey, B. Weissbach. Ein weiteres Gegenbeispiel zur Borsukschen Vermutung. Univ. Magdeburg, Fakultät für Mathematik, Preprint 31/97, 1997.
  16. D.S. Grigor'ev, A.O. Ivanov, A.A. Tuzhilin. The Gromov–Hausdorff Distances to Simplexes. Chebyshevskii Sbornik, vol. 20, no. 2, pp. 100–114, 2019. arXiv:1906.09644, 2019.
  17. N. M. Gulevich. On measure of nonconvexity and Jung constant. Journal of Mathematical Sciences, vol. 81, no. 2, pp. 2562–2566, 1996. DOI:10.1007/BF02362426.
  18. H. Hadwiger. Überdeckung einer Menge durch Mengen kleineren Durchmessers. Commentarii Mathematici Helvetici, vol. 18, pp. 73–75, 1945. DOI:10.1007/BF02568103.
  19. A. Hatcher. Algebraic Topology. Cambridge University Press, Cambridge, 2002. Hatcher's notes.
  20. A. Hinrichs. Spherical codes and Borsuk's conjecture. Discrete Mathematics, vol. 243, no. 1–3, pp. 253–256, 2002. DOI:10.1016/S0012-365X(01)00202-3.
  21. A. Hinrichs, C. Richter. New sets with large Borsuk numbers. Discrete Mathematics, vol. 270, no. 1–3, pp. 137–147, 2003. DOI:10.1016/S0012-365X(02)00833-6.
  22. A. O. Ivanov, A. A. Tuzhilin. Gromov–Hausdorff Distance, Irreducible Correspondences, Steiner Problem, and Minimal Fillings. arXiv:1604.06116, 2016.
  23. A. O. Ivanov, A. A. Tuzhilin. The Gromov–Hausdorff Distance between Simplexes and Two-Distance Spaces. arXiv:1907.09942, 2019.
  24. A. O. Ivanov, A. A. Tuzhilin. Solution to Generalized Borsuk Problem in Terms of the Gromov–Hausdorff Distances to Simplexes. arXiv:1906.10574, 2019.
  25. A. O. Ivanov, A. A. Tuzhilin. The Gromov–Hausdorff Distances between Simplexes and Ultrametric Spaces. arXiv:1907.03828, 2019.
  26. T. Jenrich. On the counterexamples to Borsuk's conjecture by Kahn and Kalai. arXiv:1809.09612, 2018.
  27. T. Jenrich, A. E. Brouwer. A 64-dimensional counterexample to Borsuk's conjecture. The Electronic Journal of Combinatorics, vol. 21, no. 4, #P4.29, 2014. arXiv:1308.0206. EJC. DOI:10.37236/4069.
  28. Y. Ji. An AI Generated Counterexample to Borsuk Problem in Dimension 63. arXiv:2608.12561v2, 2026.
  29. H. W. Jung. Uber die kleinste Kugel, die eine raumliche Figur einschliesst. Journal fur die reine und angewandte Mathematik, vol. 123, pp. 241–257, 1901. DOI:10.1515/crll.1901.123.241.
  30. J. Kahn, G. Kalai. A counterexample to Borsuk's conjecture. Bulletin of the American Mathematical Society, vol. 29, no. 1, pp. 60–62, 1993. arXiv:math/9307229.
  31. V. L. Klee. Circumspheres and inner products. Mathematica Scandinavica, vol. 8, no. 2, pp. 363–370, 1960. DOI:10.7146/math.scand.a-10618.
  32. J. Kleinberg, É. Tardos. Algorithm Design. Pearson Education Limited, Harlow, 2013.
  33. S. Lim, F. Mémoli, Z. Smith. The Gromov–Hausdorff distance between spheres. Geometry & Topology, vol. 27, no. 9, pp. 3733–3800, 2023. arXiv:2105.00611. DOI:10.2140/gt.2023.27.3733.
  34. L. A. Lusternik, L. G. Schnirelmann. Topological Methods in Variational Problems. Issled. Inst. Matem. i Mekh. pri I MGU, Moscow, 1930.
  35. I. N. Mikhailov. Ultrametric spaces and clouds. arXiv:2501.19346v1, 2025.
  36. O. R. Musin. Borsuk's conjecture for two-distance sets and its equivalent formulation for graphs. arXiv:2511.03668, 2025.
  37. A. Nilli. On Borsuk's problem. In: Jerusalem Combinatorics '93, Contemporary Mathematics, vol. 178, AMS, Providence, RI, pp. 209–210, 1994. DOI:10.1090/conm/178/01901.
  38. O. Pikhurko. Borsuk's conjecture fails in dimensions 321 and 322. arXiv:math/0202112, 2002.
  39. A. M. Raigorodskii. On the dimension in Borsuk's problem. Russian Mathematical Surveys, vol. 52, no. 6, pp. 1324–1325, 1997. Math-Net.Ru. DOI:10.1070/RM1997v052n06ABEH002184.
  40. A. M. Raigorodskii. On a bound in Borsuk's problem. Russian Mathematical Surveys, vol. 54, no. 2, pp. 453–454, 1999. Math-Net.Ru. DOI:10.1070/RM1999v054n02ABEH000146.
  41. A. M. Raigorodskii. Around Borsuk's hypothesis. Journal of Mathematical Sciences, vol. 154, no. 4, pp. 604–623, 2008. DOI:10.1007/s10958-008-9196-y.
  42. A. H. Stone. Paracompactness and product spaces. Bulletin of the American Mathematical Society, vol. 54, no. 10, pp. 977–982, 1948. DOI:10.1090/S0002-9904-1948-09118-2.
  43. A. Tolmachev, V. Voronov. Reducing the upper bound for the Borsuk number in R4 to 8. arXiv:2605.19068, 2026.
  44. A. A. Tuzhilin. Calculation of Minimum Spanning Tree Edges Lengths using Gromov–Hausdorff Distance. arXiv:1605.01566v1, 2016.
  45. B. Weissbach. Sets with large Borsuk number. Beiträge zur Algebra und Geometrie, vol. 41, no. 2, pp. 417–423, 2000. EMIS.