Cones and polytopes of geleralized metrics

E. I. Deza

Čebyševskij sbornik, Tome 20 (2019) no. 2, pp. 140-155.

Résumé

In this paper the problems of construction and research of cones and polytopes of generalized metric structures are considered: finite quasisemimetrics, which are oriented analogs of classical — symmetric — case of semimetrics, and finite $m$-semimetrics, which are multidimensional analogs of classical — two-dimensional — case of semimetrics. In the introduction the background of the research is considered, examples of use of metrics, quasimetrics and $m$-metrics in Mathematics and in Applications are given, a review of main ideas and results presented in the article is represented. In the first section definitions of main generalized metric structures considered in the paper are given: finite metrics and semimetrics, their oriented analogs — finite quasimetrics and quasisemimetrics, and their multidimensional analogs — finite $m$-metrics and $m$-semimetrics. In the second section classical examples of the corresponding generalized metric structures are given. The concept of a metric is shown by four basic examples (discrete metric — Hausdorff metric — symmetric difference metric — path metric of connected graphs). For the oriended case four corresponding quasimetrics are presented, while for the multidimensional case four corresponding $m$-metrics are constructed. In the third section an interesting example of a special case of quasimetrics is reviewed: the mean first passage time for Markov's chains. During the analysis of properties of this special structure its connections with weightable quasimetrics, partial metrics and other, rather exotic, metric structures are shown. In the fourth section the most important special cases of semimetrics are considered: cuts and multicuts. Their oriented and multidimensional analogs are constructed: oriented cuts, oriented multicuts and also partition $m$-semimetrics. In the fifth section creation of cones and polytopes of the considered generalized metric structures is carried out. Metric and cut cones and polytopes on $n$ points are considered. The oriented and multidimensional analogs of these cones and polytopes are constructed. The properties of these classes of generalized discrete metric structures are marked out. Special attention is paid to the questions of symmetries of the constructed objects. Results of the calculations devoted to cones of semimetrics, cuts, quasisemimetrics, oriented cuts and multicuts, $m$-semimetrics and partition $m$-semimetrics on small number of points (3, 4, 5 and 6 points) are presented. In fact, the dimension of an object, the number of its extreme rays (vertices) and their orbits, the number of its facets and their orbits, the diameters of the skeleton and the the ridge graph of the constructed cones and polyhedrons are specified. In the conclusion the main research results are presented.

Détail

Keywords: Semimetric, cut, multicut, cones and polytopes of semimetrics and cuts, quasisemimetric, oriented cut and multicut, cones and polytopes of quasisemimetrics, oriented cuts and multicuts, $m$-semimetric, partition $m$-semimetric, cones and polytopes of $m$-semimetrics and partition $m$-semimetrics.

Bibliographie

[1] Deza M. M., Deza E. I., Dutour Sikirić M., “Polyhedral structures associated with quasi-metrics”, Chebyshevskii sbornik, 16:2 (2015), 79–92 | MR | Zbl

[2] Kudryashov B. D., Information Theory, Piter, StPb, 2009

[3] Lidovskii V. V., Information Theory, Sputnik, M., 2004

[4] Shannon C. E., A Mathematical Theory of Communication, IL, M., 1948

[5] M. Charikar, K. Makarychev, V. Makarychev, “Directed metrics and directed graph partitioning problem”, Proc. of 11-th ACM-SIAM Symp. on Discrete Algorithms, 2006, 51–60 | MR | Zbl

[6] P. Chebotarev, “Studying new classes of graph metrics”, Proceedings of the SEE Conference "Geometric Science of Information", GSI-2013, Lecture Notes in Computer Science, 8085, 2013, 207–214 | MR | Zbl

[7] P. Chebotarev, R. Agaev, “Forest matrices around the Laplacian matrix”, Linear Algebra and its Applications, 356 (2002), 253–274 | MR | Zbl

[8] P. Chebotarev, E. Deza, “Hitting time quasi-metric and its forest representation”, Optimization Letters, 2018 | DOI | MR

[9] P. Chebotarev, E. Shamis, The forest metric for graph verticies, 2006, arXiv: math/0602573 [math.CO] | MR

[10] P. Chebotarev, E. Shamis, Matrix forest theorems, 2006, arXiv: math/0602070 [math.CO]

[11] P. Chebotarev, E. Shamis, “On proximity measures for graph vertices”, Automation and Remote Control, 59 (1998), 1443–1459 | MR | Zbl

[12] P. Chebotarev, E. Shamis, “The matrix-forest theorem and measuring relations in small social groups”, Automation and Remote Control, 58 (1997), 1505–1514 | MR | Zbl

[13] M. M. Deza, E. I. Deza, Encyclopedia of Distances, 4-rd edition, Springer-Verlag, Berlin, 2016 | MR | Zbl

[14] M. M. Deza, E. I. Deza, “Cones of partial metrics”, Contrib. Discrete Math., 6:1 (2011), 26–47 | MR | Zbl

[15] M. M. Deza, E. I. Deza, J. Vidali, “Cones of weighted and partial metrics”, Proceedings of the International Conference on Algebra, 2010, 177–197 | MR

[16] M. M. Deza, M. Dutour, E. I. Deza, Generalizations of finite metrics and cuts, World Scientific, 2016 | MR | Zbl

[17] M. M. Deza, M. Dutour, E. I. Panteleeva, “Small cones of oriented semi-metrics”, Forum for Interdisciplinary Mathematics Proceedings on Statistics, Combinatorics and Related Areas, American Journal of Mathematical and Management Sciences, 22, 2002 | MR

[18] M. M. Deza, V. P. Grishukhin, E. I. Deza, “Cones of weighted quasi-metrics, weighted quasi-hypermetrics and of oriented cuts”, Mathematics of Distances and Applications, ITEA, Sofia, 2012, 31–53 | MR

[19] M. M. Deza, M. Laurent, Geometry of cuts, metrics, Springer-Verlag, Berlin, 1997 | MR | Zbl

[20] M. M. Deza, E. I. Panteleeva, “Quasi-semi-metrics, oriented multi-cuts and related polyhedra”, European Journal of Combinatorics, 21:6 (2000), 777–795 | MR | Zbl

[21] M. M. Deza, I. G. Rosenberg, “$n$-semimetrics”, European Journal of Combinatorics, 21:6, Special Issue Discrete Metric Spaces (2000), 797–806 | MR | Zbl

[22] P. G. Doyle, J. L. Snell, Random Walks and Electric Networks, Mathematical Association of America, Washington D. C., 1984 | MR | Zbl

[23] M. Fréchet, “Sur quelques points du calcul fonctionnel”, Rend. Circolo mat. Palermo, 22 (1906), 1–74 | Zbl

[24] A. D. Gvishiani, V. A. Gurvich, “Metric and ultrametric spaces of resistances”, Russian Mathematical Surveys, 42 (1987), 235–236 | MR | Zbl

[25] F. Hausdorff, Grundzüge der Mengenlehre, Leipzig, 1914 | MR

[26] D. J. Klein, M. Randic, “Resistance distance”, Journal of Mathematical Chemistry, 1993, no. 12, 81–95 | MR

[27] A. K. Seda, “Quasi-metrics and the semantic of logic programs”, Fundamenta Informaticaem, 29 (1997), 97–117 | MR | Zbl

[28] G. E. Sharpe, “Solution of the $(m+1)$-terminal resistive network problem by means of metric geometry”, Proceedings of the First Asilomar Conference on Circuits and Systems (Pacific Grove, CA), 1967, 319–328 | MR

[29] W. A. Wilson, “On quasi-metric spaces”, American J. of Math., 53 (1931), 575–681 | MR