Corollary 5.12 — isometric dimension of the m-cube
ProvedGeometryOfGraphs.Cube.corollary_5_12graph-dimensionhypercubep2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and let the -cube be the graph of binary strings of length , adjacent when they differ in one coordinate. Its isometric dimension is exactly :
Thus no isometric realization in any real normed space of lower dimension is possible, while an isometric realization in dimension exists.
Formalization Note The printed proof uses an isometric -cycle for the lower bound when ; the case is the two-vertex graph and is included directly.
Preamble
import Definitions.Def_GeometryOfGraphs_Cube_IsometricDimension import Definitions.Def_GeometryOfGraphs_Cube_Hypercube set_option autoImplicit false
Formal statement
namespace GeometryOfGraphs.Cube /-- Corollary 5.12: the `m`-cube has isometric dimension `m`. -/ theorem corollary_5_12 (m : ℕ) (hm : 1 ≤ m) : isoDim (hypercube 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, Corollary 5.12; https://doi.org/10.1007/BF01200757
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.