Edge contraction and exit collapse force geodesic convexity
ProvedRayBundle.geodesic_mem_of_retractiongeodesicsgraph-theorymetric-geometrymetric-graphs
Let be a connected simple graph, , and a map fixing every vertex of . Suppose whenever are adjacent, and whenever , , and are adjacent. Then every shortest walk with both endpoints in has all its vertices in . The statement needs only these local conditions on ; it does not require a global range condition .
Preamble
import Mathlib.Combinatorics.SimpleGraph.Metric
Formal statement
theorem RayBundle.geodesic_mem_of_retraction {V : Type*} {X : SimpleGraph V}
(hX : X.Connected) (L : Set V) (r : V → V)
(hfix : ∀ v ∈ L, r v = v)
(hstep : ∀ {a b}, X.Adj a b → X.dist (r a) (r b) ≤ 1)
(hexit : ∀ {a b}, a ∈ L → b ∉ L → X.Adj a b → r b = a)
{a b : V} (w : X.Walk a b) (hw : w.length = X.dist a b)
(ha : a ∈ L) (hb : b ∈ L) : ∀ v ∈ w.support, v ∈ L := by sorry
Source
General graph convexity criterion proved in the supplied Lean development. Its application to ladder convexity is motivated by Proposition 4.2 of Nicholas Touikan, On geodesic ray bundles in hyperbolic groups (2018). https://arxiv.org/abs/1706.01979