simple_graph_hypercube
def
The hypercube graph Q_n on vertex set Fin n → Bool, where two vertices are adjacent if and only if they differ at exactly one coordinate.
Statement
def simple_graph_hypercube (n : ℕ) : SimpleGraph (Fin n → Bool)- Defined in
- arXiv:2610.18463 Question 5.4
- Verified
- 25 Oct 2026
- Axioms
- none listed
- Used by 8
- exists_hypercube_coilFor every n ≥ 2, there exists a coil in the hypercube Q_n.
- is_hypercube_squareA subset of 4 vertices in the hypercube Q_n is a square if its induced subgraph is isomorphic to the 4-cycle C_4.
- op_300_hypercube_two_leap_group_cardThe 2-dimensional hypercube graph Q₂ (the 4-cycle C₄) has leap group of cardinality 8.
- simple_graph_hypercube_coordinate_flipThe permutation of the vertices of the hypercube Q_n that inverts a single coordinate i.
- hypercube_degree_countThe degree count y_m is the number of vertices x in the complement of S having exactly m neighbors in S.
- hypercube_max_coil_disjoint_squares_posFor n ≥ 13, if S is a maximum coil in Q_n with degree count y_0 > 0, then the number F_5 of squares disjoint from S is strictly positive.
- op_300_hypercube_one_leap_group_cardThe hypercube graph Q₁ (the path K₂) has leap group of cardinality 2.
- hypercube_coilA subset S of vertices in the hypercube Q_n is a coil if it has size at least 4 and its induced subgraph is isomorphic to a cycle graph of…
Read back from the Lean
The definition simple_graph_hypercube n defines a simple graph whose vertices are functions u : Fin n → Bool, where edges are generated (via SimpleGraph.fromRel) by the relation that there exists a unique index i : Fin n such that u i ≠ v i. Two vertices u and v are adjacent if and only if u ≠ v and there exists a unique i : Fin n such that u i ≠ v i.
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 hypercube graph Q_n on vertices Fin n → Bool. -/ def simple_graph_hypercube (n : ℕ) : SimpleGraph (Fin n → Bool) := SimpleGraph.fromRel (fun u v => ∃! i : Fin n, u i ≠ v i)