Weakly modular graphs and nonpositive curvature

Abstract

This article investigates structural, geometrical, and topological characterizations and properties of weakly modular graphs and of cell complexes derived from them. The unifying themes of our investigation are various `nonpositive curvature' and `local-to-global' properties and characterizations of weakly modular graphs and their subclasses. Weakly modular graphs have been introduced as a far-reaching common generalization of median graphs (and more generally, of modular and orientable modular graphs), Helly graphs, bridged graphs, and dual polar graphs occurring under different disguises in several seemingly-unrelated fields of mathematics: Metric graph theory, Geometric group theory, Incidence geometries and buildings, Theoretical computer science and combinatorial optimization. We give a local-to-global characterization of weakly modular graphs and their subclasses in terms of simple connectedness of associated triangle-square complexes and specific local combinatorial conditions. In particular, we revisit characterizations of dual polar graphs by Cameron and by Brouwer-Cohen. We also show that (disk-)Helly graphs are precisely the clique-Helly graphs with simply connected clique complexes. With $l_1$-embeddable weakly modular and sweakly modular graphs we associate high-dimensional cell complexes, having several strong topological and geometrical properties (contractibility and the CAT(0) property). Their cells have a specific structure: they are basis polyhedra of even $△$-matroids in the first case and orthoscheme complexes of gated dual polar subgraphs in the second case. We resolve some open problems concerning subclasses of weakly modular graphs: we prove a Brady-McCammond conjecture about CAT(0) metric on the orthoscheme complexes of modular lattices; we answer Chastand's question about prime graphs for pre-median graphs.

to appear in Mem. Amer. Math. Soc.,

References in corpus (4)

• Initialization of lattice Boltzmann models with the help of the numerical Chapman-Enskog expansion
• Cop and robber game and hyperbolicity
• A combinatorial non-positive curvature I: weak systolicity
• Discrete Convexity and Polynomial Solvability in Minimum 0-Extension Problems

Cited by in corpus (18)

• Medians in median graphs and their cube complexes in linear time
• Obstructions to a small hyperbolicity in Helly graphs
• L-convexity on graph structures
• Hypercellular graphs: partial cubes without $Q_3^{-}$ as partial cube minor
• Helly groups
• Graphs with convex balls
• First-order logic axiomatization of metric graph theory
• Coarse cubical rigidity
• Graphs with $G^p$-connected medians
• Discrete Convexity and Polynomial Solvability in Minimum 0-Extension Problems
• ABC(T)-graphs: an axiomatic characterization of the median procedure in graphs with connected and G${}^2$-connected medians
• Lucas sequences in t-uniform simplicial complexes
• Weak Modularity and ${\tilde{A}}_n$ Buildings
• Boundary rigidity of finite CAT(0) cube complexes
• Distance labeling schemes for $K_4$-free bridged graphs
• A criterion for a locally distributive semilattice to have CAT(0) orthoscheme complex
• Quadratic isoperimetric inequality for 7-located simplicial complexes
• Recurrence relations in (s,t)-uniform simplicial complexes