Proof of Corollary 5.12 — cube embeds in ℓ₁ to dimension m
ProvedGeometryOfGraphs.Cube.cube_l1_embeddinghypercubemetric-embeddingsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
For every , the -cube embeds isometrically in : there is a coordinate map such that for every pair of cube vertices ,
This is the upper-bound assertion in the proof of Corollary 5.12. The zero-dimensional instance is a single vertex.
Preamble
import Definitions.Def_GeometryOfGraphs_Cube_Hypercube set_option autoImplicit false
Formal statement
namespace GeometryOfGraphs.Cube
/-- The cube embeds isometrically in `ℓ₁^m`. -/
theorem cube_l1_embedding (m : ℕ) :
∃ φ : (Fin m → Bool) → (Fin m → ℝ), ∀ x y,
(∑ k : Fin m, |φ x k - φ y k|) = ((hypercube m).dist x y : ℝ) := 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, proof of Corollary 5.12, first sentence; https://doi.org/10.1007/BF01200757
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.