Section 5.1 — isometric-subgraph dimension monotonicity
ProvedGeometryOfGraphs.Cube.isometric_subgraph_monotonicitygraph-dimensionisometric-subgraphsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Suppose and are finite connected graphs and a vertex map preserves every graph distance. Then
Thus an isometric subgraph supplies a lower bound on the dimension of its containing graph.
Preamble
import Definitions.Def_GeometryOfGraphs_Cube_IsometricDimension set_option autoImplicit false
Formal statement
namespace GeometryOfGraphs.Cube
/-- The dimension of an isometric subgraph is at most the dimension of its host graph. -/
theorem isometric_subgraph_monotonicity {V W : Type*}
[Fintype V] [Fintype W] (G : SimpleGraph V) (J : SimpleGraph W)
(hG : G.Connected) (hJ : J.Connected) (f : W → V)
(hf : ∀ x y, G.dist (f x) (f y) = J.dist x y) :
isoDim J ≤ isoDim G := by sorry
end GeometryOfGraphs.Cube
Source
N. Linial, E. London, Y. Rabinovich, The geometry of graphs and some of its algorithmic applications, Combinatorica 15 (1995), p. 230, Section 5.1, paragraph beginning “J is an isometric subgraph”; https://doi.org/10.1007/BF01200757
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.