Graphs with convex balls - Optimisation Combinatoire Access content directly
Preprints, Working Papers, ... Year : 2023

Graphs with convex balls

Abstract

In this paper, we investigate the graphs in which all balls are convex and the groups acting on them geometrically (which we call CB-graphs and CB-groups). These graphs have been introduced and characterized by Soltan and Chepoi (1983) and Farber and Jamison (1987). CB-graphs and CB-groups generalize systolic (alias bridged) and weakly systolic graphs and groups, which play an important role in geometric group theory. We present metric and local-to-global characterizations of CB-graphs. Namely, we characterize CB-graphs $G$ as graphs whose triangle-pentagonal complexes $X(G)$ are simply connected and balls of radius at most $3$ are convex. Similarly to systolic and weakly systolic graphs, we prove a dismantlability result for CB-graphs $G$: we show that their squares $G^2$ are dismantlable. This implies that the Rips complexes of CB-graphs are contractible. Finally, we adapt and extend the approach of Januszkiewicz and Swiatkowski (2006) for systolic groups and of Chalopin et al. (2020) for Helly groups, to show that the CB-groups are biautomatic.
Fichier principal
Vignette du fichier
2201.01599.pdf (528.83 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-03550018 , version 1 (24-03-2024)

Identifiers

Cite

Jérémie Chalopin, Victor Chepoi, Ugo Giocanti. Graphs with convex balls. 2024. ⟨hal-03550018⟩
82 View
3 Download

Altmetric

Share

Gmail Facebook X LinkedIn More