More Web Proxy on the site http://driver.im/

research-article

Graphs of Some CAT(0) Complexes

Author:

Victor ChepoiAuthors Info & Claims

Advances in Applied Mathematics, Volume 24, Issue 2

Pages 125 - 179

Published: 01 February 2000 Publication History

Abstract

In this note, 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.

References

[1]

A.D. Alexandrov, V.A. Zalgaller, Am. Math. Soc, Providence, 1967.

[2]

A.D. Alexandrov, V.N. Berestovskii, I.G. Nikolaev, Generalized Riemannian spaces, Russian Math. Surveys, 41 (1986) 1-54.

[3]

R.P. Anstee, M. Farber, On bridged graphs and cop-win graphs, J. Combin. Theory Ser. B, 44 (1988) 22-28.

[4]

N. Aronszajn, P. Panitchpakdi, Extensions of uniformly continuous transformations and hyperconvex metric spaces, Pacific J. Math., 6 (1956) 405-439.

[5]

S.P. Avnan, Metric ternary distributive semi-lattices, Proc. Amer. Math. Soc., 12 (1961) 407-414.

[6]

W. Ballman, Singular spaces of non-positive curvature, in: Progress in Math., 81, Birkhäuser, Boston/Basel/Berlin, 1990, pp. 189-201.

[7]

H.-J. Bandelt, Retracts of hypercubes, J. Graph Theory, 8 (1984) 501-510.

[8]

H.-J. Bandelt, Networks with Condorcet solutions, European J. Oper. Res., 20 (1985) 314-326.

[9]

H.-J. Bandelt, Hereditary modular graphs, Combinatorica, 8 (1988) 149-157.

[10]

H.-J. Bandelt, V. Chepoi, A Helly theorem in weakly modular space, Discrete Math., 126 (1996) 25-39.

Digital Library

[11]

H.-J. Bandelt, J. Hedl¿́ková, Median algebras, Discrete Math., 45 (1983) 1-30.

Digital Library

[12]

H.-J. Bandelt, E. Pesch, Dismantling absolute retracts of reflexive graphs, European J. Combin., 10 (1989) 211-220.

Digital Library

[13]

H.-J. Bandelt, M. van de Vel, A fixed cube theorem for median graphs, Discrete Math., 62 (1987) 129-137.

Digital Library

[14]

H.-J. Bandelt, M. van de Vel, Embedding topological median algebras in product of dendrons, Proc. London Math. Soc., 58 (1989) 439-453.

[15]

H.-J. Bandelt, M. Van de Vel, Superextensions and the depth of median graphs, J. Combin. Theory Ser. A, 57 (1991) 187-202.

[16]

M.R. Bridson, Geodesics and curvature in metric simplicial complexes, in: Group Theory from a Geometrical Point of View, World Scientific, Singapore, 1991, pp. 373-463.

[17]

M. Bridson, and, A. Haefliger, Metric Spaces of Non-Positive Curvature, forthcoming book.

[18]

H. Busemann, Academic Press, New York, 1955.

[19]

R. Charney, Artin groups of finite type are biautomatic, Math. Ann., 292 (1992) 671-683.

[20]

R. Charney, M.W. Davis, Singular metrics of nonpositive curvature on branched covers of Riemannian manifolds, Amer. J. Math., 115 (1993) 929-1009.

[21]

R. Charney, M.W. Davis, The K(¿,1)-problem for hyperplane complements associated to infinite reflection groups, J. Amer. Math. Soc., 8 (1995) 597-627.

[22]

V. Chepoi, Classifying graphs by metric triangles, Metody Diskret. Anal., 49 (1989) 75-93.

[23]

V. Chepoi, Bridged graphs are cop-win graphs: an algorithmic proof, J. Combin. Theory Ser. B, 69 (1997) 97-100.

Digital Library

[24]

V. Chepoi, On distance-preserving and domination elimination orderings, SIAM J. Discrete Math., 11 (1998) 414-436.

Digital Library

[25]

D.¿. Djokovi¿, Distance-preserving subgraphs of hypercubes, J. Combin. Theory Ser. B, 14 (1973) 263-267.

[26]

A.W.M. Dress, R. Scharlau, Gated sets in metric spaces, Aequationes Math., 34 (1987) 112-120.

[27]

A. Dress, K. Huber, V. Moulton, Some variations on a theme by Peter Buneman, Ann. Combin., 1 (1997) 339-352.

[28]

D.B.A. Epstein, J.W. Cannon, D.F. Holt, S.V.F. Levy, M.S. Paterson, W.P. Thurston, Jones and Bartlett, Boston, 1992.

[29]

S.M. Gersten, H.B. Short, Small cancellation theory and automatic groups, Invent. Math., 102 (1990) 305-334.

[30]

S.M. Gersten, H.M. Short, Small cancellation theory and automatic groups: Part II, Invent. Math., 105 (1991) 641-662.

[31]

M. Gromov, Hyperbolic groups, in: Mathematical Sciences Research Institute Publications, 8, Springer, Berlin, 1987, pp. 75-263.

[32]

M.C. Golumbic, Academic Press, New York, 1980.

[33]

M. Farber, R.E. Jamison, On local convexity in graphs, Discrete Math., 66 (1987) 231-247.

Digital Library

[34]

J.R. Isbell, Six theorems about injective metric spaces, Comment. Math. Helv., 39 (1964) 65-74.

[35]

J.R. Isbell, Median algebra, Trans. Amer. Math. Soc., 260 (1980) 319-362.

[36]

E. Jawhari, D. Misane, M. Pouzet, Retracts: graphs and ordered sets from the metric point of view, Contemp. Math., 56 (1986) 175-225.

[37]

A.V. Karzanov, Minimum 0-extensions of graph metrics, European J. Combin., 19 (1998) 71-101.

Digital Library

[38]

A. V. Karzanov, Metrics with Finite Sets of Primitive Extensions, Universität Bielefeld SFB343, preprint 97-110, 1997.

[39]

W.A. Kirk, An abstract fixed point theorem for nonexpansive mappings, Proc. Amer. Math. Soc., 82 (1981) 640-642.

[40]

R.C. Lyndon, P.E. Schupp, Springer¿Verlag, Berlin/Heidelberg/New York, 1977.

[41]

J.-H. Mai, Y. Tang, An injective metrization for collapsible polyhedra, Proc. Amer. Math. Soc., 88 (1983) 333-337.

[42]

H.M. Mulder, 1980.

[43]

H.M. Mulder, A. Schrijver, Median graphs and Helly hypergraphs, Discrete Math., 25 (1979) 41-50.

[44]

G.A. Niblo, L.D. Reeves, The geometry of cube complexes and the complexity of their fundamental groups, Topology, 37 (1998) 621-633.

[45]

G. A. Noskov, Bicombing of Triangle Buildings, Universität Bielefeld SFB343, preprint 95-138, 1995.

[46]

R. Nowakowski, I. Rival, The smallest graph variety containing all paths, Discrete Math., 43 (1983) 223-234.

Digital Library

[47]

F. Paulin, Constructions of hyperbolic groups via hyperbolizations of polyhedra, in: Group Theory from a Geometrical Point of View, World Scientific, Singapore, 1991, pp. 313-372.

[48]

J.P. Penot, Fixed point theorem without convexity, Bull. Soc. Math. France, 60 (1979) 129-152.

[49]

L. Reeves, Rational subgroups of cubed 3-manifold groups, Michigan Math. J., 42 (1994) 109-126.

[50]

A. Quilliot, On the Helly property working as a compactness criterion on graphs, J. Combin. Theory Ser. A, 40 (1985) 186-193.

[51]

M. Sageev, Ends of group pairs and non-positively curved cube complexes, Proc. London Math. Soc., 71 (1995) 585-617.

[52]

H. Seifert, W. Threlfall, Academic Press, New York, 1980.

[53]

V. Soltan, V. Chepoi, Conditions for invariance of set diameters under d-convexification in a graph, Cybernetics, 19 (1983) 750-756.

[54]

M. van de Vel, Matching binary convexities, Topology Appl., 16 (1983) 207-235.

[55]

M. van de Vel, Elsevier, Amsterdam, 1993.

[56]

M. van de Vel, Collapsible polyhedra and median spaces, Proc. Amer. Math. Soc., 126 (1998) 2811-2818.

Cited By

Guralnik DGhrist R(2021)An optimal property of the hyperplane system in a finite cubingAutonomous Robots10.1007/s10514-020-09961-645:5(665-677)Online publication date: 1-Jun-2021
https://dl.acm.org/doi/10.1007/s10514-020-09961-6
Hayashi K(2021)A Polynomial Time Algorithm to Compute Geodesics in CAT(0) Cubical ComplexesDiscrete & Computational Geometry10.1007/s00454-019-00154-265:3(636-654)Online publication date: 1-Apr-2021
https://dl.acm.org/doi/10.1007/s00454-019-00154-2
Chalopin JChepoi V(2019)1-Safe Petri Nets and Special Cube ComplexesACM Transactions on Computational Logic10.1145/332209520:3(1-49)Online publication date: 16-Jul-2019
https://dl.acm.org/doi/10.1145/3322095
Show More Cited By

Index Terms

Graphs of Some CAT(0) Complexes
1. Mathematics of computing
  1. Discrete mathematics
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Relating CAT(0) cubical complexes and flag simplicial complexes
Abstract
Given a finite CAT ( 0 ) cubical complex, we define a flag simplicial complex associated to it, called the crossing complex. We show that the crossing complex holds much of the combinatorial information of the original cubical complex: ...
Planar graphs without cycles of length 4 or 5 are ( 2 , 0 , 0 ) -colorable

Let d 1 , d 2 , , d k be k nonnegative integers. A graph G = ( V , E ) is ( d 1 , d 2 , , d k ) -colorable, if the vertex set V of G can be partitioned into subsets V 1 , V 2 , , V k such that the subgraph G V i induced by V i has maximum degree at most ...
Independence complexes of chordal graphs

We show that the independence complex I(G) of an arbitrary chordal graph G is either contractible or is homotopy equivalent to the finite wedge of spheres of dimension at least the domination number of G minus 1. Also it is shown that every finite wedge ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Advances in Applied Mathematics

Advances in Applied Mathematics Volume 24, Issue 2

Feb. 2000

91 pages

ISSN:0196-8858

Editor:
Gian-Carlo Rota
Academic Press, Cambridge, UK

Issue’s Table of Contents

Copyright © Academic Press.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 February 2000

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Guralnik DGhrist R(2021)An optimal property of the hyperplane system in a finite cubingAutonomous Robots10.1007/s10514-020-09961-645:5(665-677)Online publication date: 1-Jun-2021
https://dl.acm.org/doi/10.1007/s10514-020-09961-6
Hayashi K(2021)A Polynomial Time Algorithm to Compute Geodesics in CAT(0) Cubical ComplexesDiscrete & Computational Geometry10.1007/s00454-019-00154-265:3(636-654)Online publication date: 1-Apr-2021
https://dl.acm.org/doi/10.1007/s00454-019-00154-2
Chalopin JChepoi V(2019)1-Safe Petri Nets and Special Cube ComplexesACM Transactions on Computational Logic10.1145/332209520:3(1-49)Online publication date: 16-Jul-2019
https://dl.acm.org/doi/10.1145/3322095
Dragan FKhler EAlrasheed H(2017)Eccentricity approximating treesDiscrete Applied Mathematics10.1016/j.dam.2017.07.017232:C(142-156)Online publication date: 11-Dec-2017
https://dl.acm.org/doi/10.1016/j.dam.2017.07.017
Hirai H(2016)Discrete convexity and polynomial solvability in minimum 0-extension problemsMathematical Programming: Series A and B10.1007/s10107-014-0824-7155:1-2(1-55)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1007/s10107-014-0824-7
Dragan FKöhler EAlrasheed H(2016)Eccentricity Approximating TreesRevised Selected Papers of the 42nd International Workshop on Graph-Theoretic Concepts in Computer Science - Volume 994110.1007/978-3-662-53536-3_13(145-157)Online publication date: 22-Jun-2016
https://dl.acm.org/doi/10.1007/978-3-662-53536-3_13
Herrmann SKoolen JLesser AMoulton VWu T(2015)Optimal realizations of two-dimensional, totally-decomposable metricsDiscrete Mathematics10.1016/j.disc.2015.02.008338:8(1289-1299)Online publication date: 6-Aug-2015
https://dl.acm.org/doi/10.1016/j.disc.2015.02.008
Bandelt HChepoi VEppstein D(2015)Ramified Rectilinear PolygonsDiscrete & Computational Geometry10.1007/s00454-015-9743-554:4(771-797)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.1007/s00454-015-9743-5
Hirai H(2014)The Maximum Multiflow Problems with Bounded FractionalityMathematics of Operations Research10.1287/moor.2013.060039:1(60-104)Online publication date: 1-Feb-2014
https://dl.acm.org/doi/10.1287/moor.2013.0600
Hirai HKhanna S(2013)Discrete convexity and polynomial solvability in minimum 0-extension problemsProceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms10.5555/2627817.2627944(1770-1788)Online publication date: 6-Jan-2013
https://dl.acm.org/doi/10.5555/2627817.2627944
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents