Weakly Modular Graphs and Nonpositive Curvature.

Format:

Book

Author/Creator:

Chalopin, Jérémie.

Contributor:

Chepoi, Victor.

Hirai, Hiroshi.

Series:

Memoirs of the American Mathematical Society ; no. 1309.

Memoirs of the American Mathematical Society, 0065-9266 ; number 1309

Language:

English

Subjects (All):

Graph theory.

Curvature.

Distance geometry.

Combinatorial optimization.

Physical Description:

1 online resource (172 pages)

Edition:

1st ed.

Place of Publication:

Providence : American Mathematical Society, 2021.

Summary:

"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 (1-skeletons, collinearity graphs, covering graphs, domains, etc.) 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 l1-embeddable weakly modular and sweakly modular graphs we associate high-dimensional cell complexes, having several strong topological and geometrical properties (contractibility and the CAT([empty set]) 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([empty set]) metric on the orthoscheme complexes of modular lattices; we answer Chastand's question about prime graphs for pre-median graphs. We also explore negative curvature for weakly modular graphs"-- Provided by publisher.

Contents:

Cover

Title page

Chapter 1. Introduction

1.1. Avant-propos

1.2. Motivation

1.3. Main results

Acknowledgments

Chapter 2. Preliminaries

2.1. Basic notions

2.2. Further notions

Chapter 3. Local-to-Global Characterization

3.1. Main results

3.2. Weakly modular graphs: proofs

3.3. Helly and clique-Helly graphs: proofs

3.4. A note on meshed graphs

Chapter 4. Pre-Median Graphs

4.1. Main results

4.2. Prime pre-median graphs

4.3. Examples

4.4. ₁-Weakly modular graphs

4.5. ( ) is contractible

Chapter 5. Dual Polar Graphs

5.1. Main results

5.2. Proof of Theorem 5.2

5.3. Proof of Theorems 5.3 and 5.4

Chapter 6. Sweakly Modular Graphs

6.1. Main results

6.2. A lattice-theoretical characterization of swm-graphs

6.3. Boolean pairs and Boolean-gated sets

6.4. Barycentric graph *

6.5. Thickening ^{Δ}

6.6. Δ-gates and geodesic extension property

6.7. Normal Boolean-gated paths

6.8. Euclidean buildings of type C_{ }

6.9. Application I: Biautomaticity of swm-groups

6.10. Application II: 2-approximation to 0-extension problem on swm-graphs

Chapter 7. Orthoscheme Complexes of Modular Lattices and Semilattices

7.1. Main results

7.2. Boolean and complemented modular lattices

7.3. Distributive and modular lattices

7.4. Proof of Theorem 7.2

7.5. Proof of Propositions 7.5 and 7.6

7.6. Proof of Proposition 7.4

Chapter 8. Orthoscheme Complexes of Swm-Graphs

8.1. Main results

8.2. Examples

8.3. Preliminary results

8.4. ₁-metrization

8.5. _{∞}-metrization

8.6. ₂-metrization

8.7. ( ) is contractible

Chapter 9. Metric Properties of Weakly Modular Graphs

9.1. Quadratic isoperimetric inequality

9.2. Hyperbolicity

9.3. BFS gives a distance-preserving ordering

9.4. Weakly modular complex

Bibliography.

Back Cover.

Notes:

Description based on publisher supplied metadata and other sources.

"November 2020, volume 268, number 1309 (sixth of 6 numbers)."

Includes bibliographical references.

ISBN:

9781470463496

1470463490

OCLC:

1343247673