Convex Polyhedra of Binary Trees and their Symmetries
https://doi.org/10.22405/2226-8383-2025-26-2-101-124
Abstract
Problem of finding minimal parametric fillings of a finite metric space 𝑀 can be reduced to classical linear programming. The set of admissible values of the dual problem is a convex polyhedron Λ𝐺 that depends on the filling type 𝐺, i.e., on a tree, whose set of degree 1 vertices equals 𝑀, and all other vertices have degree 3 (such trees are referred as binary trees connecting 𝑀). Vertices of this polyhedron have an important role in minimal filling weight calculation.
Generally speaking, isomorphic binary trees connecting the same space 𝑀 correspond to different polyhedra. In the present paper a complete answer on the relations between such polyhedra is obtained. Besides, the question on the structure of the set 𝑈 obtained as the union
of the vertices of all polyhedra Λ𝐺 over all binary trees connecting a given set 𝑀. This set 𝑈 = 𝑈(𝑚) depends on the number of points 𝑚 in the set 𝑀. It turns out that the set 𝑈(𝑚) is convex for 𝑚 ⩽ 6, i.e., it is a vertex set of a convex polyhedron. Convexity of 𝑈(𝑚) for other 𝑚 is an open question.
About the Authors
Alexandr Olegovich Ivanov
Lomonosov Moscow State University; Bauman Moscow State Technical University
Russian Federation
Russian Federation
doctor of physical and mathematical sciences, professor
Dmirtii Alexeevich Markhanov
Lomonosov Moscow State University
Russian Federation
Russian Federation
References
1. Ivanov, A.O., Tuzhilin, A.A., 2003, Extreme Networks Theory, Moscow-Izhevsk: Regul. i Khaot. Dinamika [in Russian].
2. Ivanov, A.O., Tuzhilin, A.A., 2012, “One-dimensional Gromov Minimal Filling Problem”, Sbornik Math., vol. 203, no. 5, pp. 65–118. DOI: https://doi.org/10.1070/SM2012v203n05ABEH004239.
3. Ivanov, A.O., Ovsyannikov, Z.N., Strelkova, N.P., Tuzhilin, A.A., 2012, “One-dimensional Minimal Fillings with Negative Edge Weights”, Moscow Univ. Math. Bull., vol. 67, no. 5–6, pp. 189–194. DOI: https://doi.org/10.3103/S0027132212050014.
4. Ivanov, A., Tuzhilin, A., 2021, “Dual Linear Programming Problem and One-Dimensional Gromov Minimal Fillings of Finite Metric Space”, in Trends in Mathematics, Cham: Springer, pp. 165–182. arXiv:1907.03828 [math.MG] (2019).
5. Gromov, M., 1983, “Filling Riemannian Manifolds”, J. Diff. Geom., vol. 18, no. 1, pp. 1–147. DOI: 10.4310/jdg/1214509283.
6. Ivanov, A.O., Tuzhilin, A.A., 2014, “Minimal Fillings of Finite Metric Spaces: The State of the Art”, in Discrete Geometry and Algebraic Combinatorics, AMS, vol. 625, pp. 9–35.
7. Bednov, B.B., Borodin, P.A., 2014, “Banach Spaces that Realize Minimal Fillings”, Sb. Math., vol. 205, no. 4, pp. 459–475. DOI: https://doi.org/10.1070/SM2014v205n04ABEH004383.
8. Eremin, A.Yu., 2013, “A Formula for the Weight of a Minimal Filling of a Finite Metric Space”, Sb. Math., vol. 204, no. 9, pp. 1285–1306. DOI: https://doi.org/10.1070/SM2013v204n09ABEH004340.
9. Shcherbakov, O.S., 2022, “Polyhedra of Binary Trees, Structure of the Polyhedron for a Tree of the “Snake” Type”, Chebyshev. Sbornik, vol. 23, no. 4, pp. 136–151 [in Russian]. DOI: https://doi.org/10.22405/2226-8383-2022-23-4-136-151.
10. Shcherbakov, O.S., 2025, “Upper Estimates on the Multiplicities of Irreducible Multitours for Some Binary Trees”, Moscow Univ. Math. Bull. [in Russian, to appear].
11. Ivanov, A.O., Shcherbakov, O.S., 2024, “Existence of Irreducible Multitours of Multiplicity 2”, Chebyshev. Sbornik, vol. 25, no. 3, pp. 101–117.
12. Bednov, B.B., 2017, “The Length of Minimal Filling for a Five-Point Metric”, Moscow University Math. Bull., vol. 72, no. 6, pp. 221–225. DOI: https://doi.org/10.3103/S0027132217060018.
13. Vasiliev, F.P., Ivanitskii, A.Yu., 1998, Linear Programming, Moscow: Factorial Press.
14. Hwang, F.K., 1986, “A Linear Time Algorithm for Full Steiner Trees”, Operations Research Letters, vol. 4, no. 5, pp. 235–237. DOI: https://doi.org/10.1016/0167-6377(86)90008-8.
15. Vinberg, E.B., 2003, A Course in Algebra, New York: AMS.
16. Malysheva, O.S., 2020, “Optimal position of compact sets and the Steiner problem in spaces with Euclidean Gromov–Hausdorff metric”, Sb. Math., vol. 211, no. 10, pp. 1382–1398. DOI:https://doi.org/10.1070/SM9361.
Review
For citations:
Ivanov A.O., Markhanov D.A. Convex Polyhedra of Binary Trees and their Symmetries. Chebyshevskii Sbornik. 2025;26(2):101-124. (In Russ.) https://doi.org/10.22405/2226-8383-2025-26-2-101-124
Views:
6
Email this article 