hypercube_red_subgraph
Given n : ℕ and an edge coloring c : (hypercube_graph n).edgeSet → Bool, hypercube_red_subgraph n c is the simple graph on vertex type Fin n → Bool where vertices u and v are adjacent if and only if there exists a proof h that u and v are adjacent in hypercube_graph n such that c ⟨s(u, v), h⟩ = true.
Statement
def hypercube_red_subgraph (n : ℕ) (c : (hypercube_graph n).edgeSet → Bool) : SimpleGraph (Fin n → Bool)- Defined in
- arXiv:2611.16243 Section 2
- Verified
- 16 Nov 2026
- Axioms
- none listed
- Built on 1
- hypercube_graphThe 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…
- Used by 1
- 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…
Read back from the Lean
Given a natural number n and an edge-coloring function c : (hypercube_graph n).edgeSet → Bool, hypercube_red_subgraph n c is the simple graph on vertices Fin n → Bool where two vertices u and v are adjacent if and only if u and v are adjacent in hypercube_graph n (witnessed by h) and the edge ⟨s(u, v), h⟩ satisfies c ⟨s(u, v), h⟩ = true.
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 spanning subgraph of Q_n formed by the edges of color red (true) under edge coloring c. -/ def hypercube_red_subgraph (n : ℕ) (c : (hypercube_graph n).edgeSet → Bool) : SimpleGraph (Fin n → Bool) where Adj u v := ∃ h : (hypercube_graph n).Adj u v, c ⟨s(u, v), h⟩ = true symm := ⟨by intro u v ⟨h, hc⟩ refine ⟨h.symm, ?_⟩ have : (⟨s(v, u), h.symm⟩ : (hypercube_graph n).edgeSet) = ⟨s(u, v), h⟩ := Subtype.ext Sym2.eq_swap rw [this] exact hc⟩ loopless := ⟨by intro u ⟨h, _⟩ exact (hypercube_graph n).loopless.irrefl u h⟩