hypercube_graph
def
The n-dimensional hypercube graph Q_n has vertex set {0, 1}^n, with two vertices adjacent if and only if their Hamming distance is 1 (they differ in exactly one coordinate).
Statement
def hypercube_graph (n : ℕ) : SimpleGraph (Fin n → Bool)- Defined in
- arXiv:2611.16243 Section 1
- Verified
- 16 Nov 2026
- Axioms
- none listed
- Used by 3
- is_antipodal_coloringGiven n : ℕ, an edge coloring c : (hypercube_graph n).edgeSet → Bool is antipodal if for all vertices u, v : Fin n → Bool, given proofs h…
- antipodal_coloring_exists_red_path_of_pair_labellingConditional form of the antipodal-coloring theorem: if for every K ≥ 2 there is no labelling of the vertices of Q_K by ordered pairs of…
- hypercube_red_subgraphGiven n : ℕ and an edge coloring c : (hypercube_graph n).edgeSet → Bool, hypercube_red_subgraph n c is the simple graph on vertex type Fin…
Read back from the Lean
hypercube_graph n is the simple graph whose vertex type is Fin n → Bool, where two vertices u and v are adjacent if and only if the Hamming distance between u and v is equal to 1.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The n-dimensional hypercube graph Q_n on {0, 1}^n with edges between vertices at Hamming distance 1. -/ def hypercube_graph (n : ℕ) : SimpleGraph (Fin n → Bool) where Adj u v := hammingDist u v = 1 symm := ⟨by intro u v h; rw [hammingDist_comm]; exact h⟩ loopless := ⟨by intro u h; rw [hammingDist_self] at h; contradiction⟩