Proposition 5.10 — isometric dimension of an even cycle
ProvedGeometryOfGraphs.Cube.proposition_5_10cyclesgraph-dimensionp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
For an integer , the cycle on vertices has isometric dimension :
This supplies the lower bound for the cube through its isometric even-cycle subgraph. The condition gives an ordinary cycle with at least four vertices.
Preamble
import Definitions.Def_GeometryOfGraphs_Cube_IsometricDimension set_option autoImplicit false
Formal statement
namespace GeometryOfGraphs.Cube
/-- Proposition 5.10: the even cycle has isometric dimension half its length. -/
theorem proposition_5_10 (m : ℕ) (hm : 2 ≤ m) :
isoDim (SimpleGraph.cycleGraph (2 * m)) = m := 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. 233, Proposition 5.10; https://doi.org/10.1007/BF01200757
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.