×

Kirszbraun-type theorems for graphs. (English) Zbl 1416.05273

Summary: The classical Kirszbraun theorem says that all 1-Lipschitz functions \(f : A \longrightarrow \mathbb{R}^n\), \(A \subset \mathbb{R}^n\), with the Euclidean metric have a 1-Lipschitz extension to \(\mathbb{R}^n\). For metric spaces \(X, Y\) we say that \(Y\) is \(X\)-Kirszbraun if all 1-Lipschitz functions \(f : A \longrightarrow Y\), \(A \subset X\), have a 1-Lipschitz extension to \(X\). We analyze the case when \(X\) and \(Y\) are graphs with the usual path metric. We prove that \(\mathbb{Z}^d\)-Kirszbraun graphs are exactly graphs that satisfies a certain Helly’s property. We also consider complexity aspects of these properties.

MSC:

05C99 Graph theory
47H09 Contraction-type mappings, nonexpansive mappings, \(A\)-proper mappings, etc.
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Akopyan, A. V.; Tarasov, A. S., A constructive proof of Kirszbraun’s theorem, Math. Notes, 84, 725-728 (2008) · Zbl 1221.47091
[2] Bandelt, H.-J.; Chepoi, V., Metric graph theory and geometry: a survey, (Surveys on Discrete and Computational Geometry (2008), AMS: AMS Providence, RI), 49-86 · Zbl 1169.05015
[3] Bandelt, H.-J.; Pesch, E., Dismantling absolute retracts of reflexive graphs, European J. Combin., 10, 211-220 (1989) · Zbl 0674.05065
[4] Benyamini, Y.; Lindenstrauss, J., Geometric Nonlinear Functional Analysis, vol. 1 (2000), AMS: AMS Providence, RI · Zbl 0946.46002
[5] Berge, C.; Duchet, P., A generalization of Gilmore’s theorem, (Recent Advances in Graph Theory (1975), Academia: Academia Prague), 49-55 · Zbl 0325.05125
[6] Bezdek, K., Classical Topics in Discrete Geometry (2010), Springer: Springer New York · Zbl 1207.52001
[7] Bobenko, A. I.; Suris, Yu. B., Discrete Differential Geometry (2008), AMS: AMS Providence, RI · Zbl 1158.53001
[8] Brehm, U., Extensions of distance reducing mappings to piecewise congruent mappings on \(R^m\), J. Geom., 16, 187-193 (1981) · Zbl 0467.51020
[9] Chalopin, J.; Chepoi, V.; Hirai, H.; Osajda, D., Weakly modular graphs and nonpositive curvature, Mem. Amer. Math. Soc. (2018), in press
[10] Chepoi, V.; Dragan, F. F.; Vaxés, Y., Core congestion is inherent in hyperbolic networks, (Proc. 28th SODA (2017), SIAM: SIAM Philadelphia, PA), 2264-2279 · Zbl 1410.68031
[11] Chepoi, V.; Estellon, B., Packing and covering of \(δ\)-hyperbolic spaces by balls, (Charikar, M.; etal., Approximation, Randomization, and Combinatorial Optimization (2007), Springer: Springer Berlin), 59-73 · Zbl 1171.05315
[12] Connelly, R.; Demaine, E. D., Geometry and topology of polygonal linkages, (Handbook of Discrete and Computational Geometry (2004), CRC Press: CRC Press Boca Raton, FL), 197-218
[13] Connelly, R.; Demaine, E. D.; Rote, G., Straightening polygonal arcs and convexifying polygonal cycles, Discrete Comput. Geom., 30, 205-239 (2003) · Zbl 1046.52016
[14] Danzer, L.; Grünbaum, B.; Klee, V., Helly’s theorem and its relatives, Proc. Sympos. Pure Math., vol. VII, 101-180 (1963), AMS: AMS Providence, RI · Zbl 0132.17401
[15] Dourado, M. C.; Protti, F.; Szwarcfiter, J. L., On Helly hypergraphs with variable intersection sizes, Ars Combin., 114, 185-191 (2014) · Zbl 1324.52007
[16] Federer, H., Geometric Measure Theory (1969), Springer: Springer New York · Zbl 0176.00801
[17] Hell, P.; Nešetřil, J., Graphs and Homomorphisms (2004), Oxford Univ. Press: Oxford Univ. Press Oxford · Zbl 1062.05139
[18] Helly, E., Über mengen konvexer körper mit gemeinschaftlichen punkten, Jahresber. Dtsch. Math.-Ver., 32, 175-176 (1923), (in German) · JFM 49.0534.02
[19] Kenyon, R., An introduction to the dimer model, (ICTP Lect. Notes XVII. ICTP Lect. Notes XVII, Trieste (2004)), 267-304 · Zbl 1076.82025
[20] Kirszbraun, M., Über die zusammenziehende und lipschitzsche transformationen, Fund. Math., 22, 77-108 (1934) · JFM 60.0532.03
[21] Lang, U., Extendability of large-scale Lipschitz maps, Trans. Amer. Math. Soc., 351, 3975-3988 (1999) · Zbl 1010.54016
[22] Lang, U.; Schroeder, V., Kirszbraun’s theorem and metric spaces of bounded curvature, Geom. Funct. Anal., 7, 535-560 (1997) · Zbl 0891.53046
[23] Linial, N., Finite metric spaces – combinatorics, geometry and algorithms, (Proc. ICM Beijing, Vol. III (2002), Higher Ed. Press: Higher Ed. Press Beijing), 573-586 · Zbl 0997.05019
[24] Matoušek, J., Lectures on Discrete Geometry (2002), Springer: Springer New York · Zbl 0999.52006
[25] Menz, G.; Tassy, M., A variational principle for a non-integrable model · Zbl 1446.82017
[26] Pak, I., Tile invariants: new horizons, Theoret. Comput. Sci., 303, 303-331 (2003) · Zbl 1052.68094
[27] Pak, I., Lectures on discrete and polyhedral geometry, monograph draft (2009), available at
[28] Pak, I.; Sheffer, A.; Tassy, M., Fast domino tileability, Discrete Comput. Geom., 56, 377-394 (2016) · Zbl 1350.68267
[29] Sheffield, S., Random surfaces, Astérisque, 304 (2005), 175 pp. · Zbl 1104.60002
[30] Tassy, M., Tiling by Bars (2014), Brown University, available at
[31] Thurston, W. P., Groups, tilings and finite state automata, (Lecture Notes. Lecture Notes, AMS Summer Meetings, Bolder, CO (1989))
[32] Valentine, F. A., A Lipschitz condition preserving extension for a vector function, Amer. J. Math., 67, 83-93 (1945) · Zbl 0061.37507
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.