Theorem 5.7 — isometric dimension as minimum implementing rank
ProvedGeometryOfGraphs.Cube.theorem_5_7graph-dimensionmatrix-rankp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a finite connected graph. Among all real matrices that implement , with the number of columns allowed to vary, its isometric dimension is the smallest matrix rank:
This characterizes the geometric invariant by linear algebra and is used for lower bounds such as the even-cycle calculation.
Formalization Note The implementation condition uses coordinatewise bounds plus attainment, so a zero-column matrix is permitted for a one-vertex graph.
Preamble
import Definitions.Def_GeometryOfGraphs_Cube_IsometricDimension import Definitions.Def_GeometryOfGraphs_Cube_Implements set_option autoImplicit false
Formal statement
namespace GeometryOfGraphs.Cube
/-- Theorem 5.7: isometric dimension is the least rank of an implementing matrix. -/
theorem theorem_5_7 {V : Type*} [Fintype V] [DecidableEq V]
(G : SimpleGraph V) (hG : G.Connected) :
isoDim G = sInf {k : ℕ | ∃ (r : ℕ) (M : Matrix V (Fin r) ℝ),
Implements G M ∧ M.rank = k} := 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. 232, Theorem 5.7; https://doi.org/10.1007/BF01200757
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.