×

zbMATH — the first resource for mathematics

Graphs of some CAT(0) complexes. (English) Zbl 1019.57001
Summary: We characterize the graphs (1-skeletons) of some piecewise Euclidean simplicial and cubical complexes having nonpositive curvature in the sense of Gromov’s CAT(0) inequality. Each such cell complex \(K\) is simply connected and obeys a certain flag condition. It turns out that if, in addition, all maximal cells are either regular Euclidean cubes or right Euclidean triangles glued in a special way, then the underlying graph \(G(K)\) is either a median graph or a hereditary modular graph without two forbidden induced subgraphs. We also characterize the simplicial complexes arising from bridged graphs, a class of graphs whose metric enjoys one of the basic properties of CAT(0) spaces. Additionally, we show that the graphs of all these complexes and some more general classes of graphs have geodesic combings and bicombings verifying the 1- or 2-fellow traveler property.

MSC:
57M07 Topological methods in group theory
20F67 Hyperbolic groups and nonpositively curved groups
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alexandrov, A. D.; Zalgaller, V. A., Intrinsic Geometry of Surfaces, Transl. Math. Monographs, 15, (1967), Am. Math. Soc Providence · Zbl 0146.44103
[2] Alexandrov, A. D.; Berestovskii, V. N.; Nikolaev, I. G., Generalized Riemannian spaces, Russian Math. Surveys, 41, 1-54, (1986) · Zbl 0625.53059
[3] Anstee, R. P.; Farber, M., On bridged graphs and cop-win graphs, J. Combin. Theory Ser. B, 44, 22-28, (1988) · Zbl 0654.05049
[4] Aronszajn, N.; Panitchpakdi, P., Extensions of uniformly continuous transformations and hyperconvex metric spaces, Pacific J. Math., 6, 405-439, (1956) · Zbl 0074.17802
[5] Avnan, S. P., Metric ternary distributive semi-lattices, Proc. Amer. Math. Soc., 12, 407-414, (1961) · Zbl 0099.02201
[6] Ballman, W., Singular spaces of non-positive curvature, (Ghys, E.; de la Harpe, P., Sur les groupes hyperboliques d’apres Mikhael Gromov, Progress in Math., 81, (1990), Birkhäuser Boston/Basel/Berlin), 189-201
[7] Bandelt, H.-J., Retracts of hypercubes, J. Graph Theory, 8, 501-510, (1984) · Zbl 0551.05060
[8] Bandelt, H.-J., Networks with Condorcet solutions, European J. Oper. Res., 20, 314-326, (1985) · Zbl 0564.90011
[9] Bandelt, H.-J., Hereditary modular graphs, Combinatorica, 8, 149-157, (1988) · Zbl 0659.05076
[10] Bandelt, H.-J.; Chepoi, V., A Helly theorem in weakly modular space, Discrete Math., 126, 25-39, (1996) · Zbl 0864.05049
[11] Bandelt, H.-J.; Hedlı́ková, J., Median algebras, Discrete Math., 45, 1-30, (1983)
[12] Bandelt, H.-J.; Pesch, E., Dismantling absolute retracts of reflexive graphs, European J. Combin., 10, 211-220, (1989) · Zbl 0674.05065
[13] Bandelt, H.-J.; van de Vel, M., A fixed cube theorem for Median graphs, Discrete Math., 62, 129-137, (1987) · Zbl 0628.05053
[14] Bandelt, H.-J.; van de Vel, M., Embedding topological Median algebras in product of dendrons, Proc. London Math. Soc., 58, 439-453, (1989) · Zbl 0682.05031
[15] Bandelt, H.-J.; Van de Vel, M., Superextensions and the depth of Median graphs, J. Combin. Theory Ser. A, 57, 187-202, (1991) · Zbl 0756.05091
[16] Bridson, M. R., Geodesics and curvature in metric simplicial complexes, (Ghys, E.; Haefliger, A.; Verjovsky, A., Group Theory from a Geometrical Point of View, (1991), World Scientific Singapore), 373-463 · Zbl 0844.53034
[17] M. Bridson, and, A. Haefliger, Metric Spaces of Non-Positive Curvature, forthcoming book. · Zbl 0988.53001
[18] Busemann, H., The Geometry of Geodesics, (1955), Academic Press New York · Zbl 0112.37002
[19] Charney, R., Artin groups of finite type are biautomatic, Math. Ann., 292, 671-683, (1992) · Zbl 0736.57001
[20] Charney, R.; Davis, M. W., Singular metrics of nonpositive curvature on branched covers of Riemannian manifolds, Amer. J. Math., 115, 929-1009, (1993) · Zbl 0804.53056
[21] Charney, R.; Davis, M. W., The K(π,1)-problem for hyperplane complements associated to infinite reflection groups, J. Amer. Math. Soc., 8, 597-627, (1995) · Zbl 0833.51006
[22] Chepoi, V., Classifying graphs by metric triangles, Metody Diskret. Anal., 49, 75-93, (1989)
[23] Chepoi, V., Bridged graphs are cop-win graphs: an algorithmic proof, J. Combin. Theory Ser. B, 69, 97-100, (1997) · Zbl 0873.05060
[24] Chepoi, V., On distance-preserving and domination elimination orderings, SIAM J. Discrete Math., 11, 414-436, (1998) · Zbl 0915.05097
[25] Djoković, D.Ž., Distance-preserving subgraphs of hypercubes, J. Combin. Theory Ser. B, 14, 263-267, (1973) · Zbl 0245.05113
[26] Dress, A. W.M.; Scharlau, R., Gated sets in metric spaces, Aequationes Math., 34, 112-120, (1987) · Zbl 0696.54022
[27] Dress, A.; Huber, K.; Moulton, V., Some variations on a theme by Peter buneman, Ann. Combin., 1, 339-352, (1997) · Zbl 0927.05078
[28] Epstein, D. B.A.; Cannon, J. W.; Holt, D. F.; Levy, S. V.F.; Paterson, M. S.; Thurston, W. P., Word Processing in Groups, (1992), Jones and Bartlett Boston
[29] Gersten, S. M.; Short, H. B., Small cancellation theory and automatic groups, Invent. Math., 102, 305-334, (1990) · Zbl 0714.20016
[30] Gersten, S. M.; Short, H. M., Small cancellation theory and automatic groups: part II, Invent. Math., 105, 641-662, (1991) · Zbl 0734.20014
[31] Gromov, M., Hyperbolic groups, (Gersten, S. M., Essays in Group Theory, Mathematical Sciences Research Institute Publications, 8, (1987), Springer Berlin), 75-263 · Zbl 0634.20015
[32] Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs, (1980), Academic Press New York · Zbl 0541.05054
[33] Farber, M.; Jamison, R. E., On local convexity in graphs, Discrete Math., 66, 231-247, (1987) · Zbl 0619.05032
[34] Isbell, J. R., Six theorems about injective metric spaces, Comment. Math. Helv., 39, 65-74, (1964) · Zbl 0151.30205
[35] Isbell, J. R., Median algebra, Trans. Amer. Math. Soc., 260, 319-362, (1980) · Zbl 0446.06007
[36] Jawhari, E.; Misane, D.; Pouzet, M., Retracts: graphs and ordered sets from the metric point of view, Contemp. Math., 56, 175-225, (1986)
[37] Karzanov, A. V., Minimum 0-extensions of graph metrics, European J. Combin., 19, 71-101, (1998) · Zbl 0894.90147
[38] A. V. Karzanov, Metrics with Finite Sets of Primitive Extensions, Universität Bielefeld SFB343, preprint 97-110, 1997. · Zbl 0946.90069
[39] Kirk, W. A., An abstract fixed point theorem for nonexpansive mappings, Proc. Amer. Math. Soc., 82, 640-642, (1981) · Zbl 0471.54027
[40] Lyndon, R. C.; Schupp, P. E., Combinatorial Group Theory, (1977), Springer-Verlag Berlin/Heidelberg/New York
[41] Mai, J.-H.; Tang, Y., An injective metrization for collapsible polyhedra, Proc. Amer. Math. Soc., 88, 333-337, (1983) · Zbl 0516.54027
[42] Mulder, H. M., The Interval Function of a Graph, Math. Centre Tracts, 132, (1980) · Zbl 0446.05039
[43] Mulder, H. M.; Schrijver, A., Median graphs and Helly hypergraphs, Discrete Math., 25, 41-50, (1979) · Zbl 0395.05058
[44] Niblo, G. A.; Reeves, L. D., The geometry of cube complexes and the complexity of their fundamental groups, Topology, 37, 621-633, (1998) · Zbl 0911.57002
[45] G. A. Noskov, Bicombing of Triangle Buildings, Universität Bielefeld SFB343, preprint 95-138, 1995.
[46] Nowakowski, R.; Rival, I., The smallest graph variety containing all paths, Discrete Math., 43, 223-234, (1983) · Zbl 0511.05059
[47] Paulin, F., Constructions of hyperbolic groups via hyperbolizations of polyhedra, (Ghys, E.; Haefliger, A.; Verjovsky, A., Group Theory from a Geometrical Point of View, (1991), World Scientific Singapore), 313-372 · Zbl 0843.20032
[48] Penot, J. P., Fixed point theorem without convexity, Bull. Soc. Math. France, 60, 129-152, (1979) · Zbl 0454.47044
[49] Reeves, L., Rational subgroups of cubed 3-manifold groups, Michigan Math. J., 42, 109-126, (1994) · Zbl 0852.57018
[50] Quilliot, A., On the Helly property working as a compactness criterion on graphs, J. Combin. Theory Ser. A, 40, 186-193, (1985) · Zbl 0575.05026
[51] Sageev, M., Ends of group pairs and non-positively curved cube complexes, Proc. London Math. Soc., 71, 585-617, (1995) · Zbl 0861.20041
[52] Seifert, H.; Threlfall, W., A Textbook of Topology, (1980), Academic Press New York · Zbl 0469.55001
[53] Soltan, V.; Chepoi, V., Conditions for invariance of set diameters under d-convexification in a graph, Cybernetics, 19, 750-756, (1983) · Zbl 0564.05037
[54] van de Vel, M., Matching binary convexities, Topology Appl., 16, 207-235, (1983) · Zbl 0543.52001
[55] van de Vel, M., Theory of Convex Structures, (1993), Elsevier Amsterdam · Zbl 0785.52001
[56] van de Vel, M., Collapsible polyhedra and Median spaces, Proc. Amer. Math. Soc., 126, 2811-2818, (1998) · Zbl 0918.52005
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.