hypercube_coil
A 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 size |S|.
Statement
def hypercube_coil (n : ℕ) (S : Finset (Fin n → Bool)) : Prop
- Defined in
- arXiv:2610.36461 Section 1
- Verified
- 29 Oct 2026
- Axioms
- none listed
- Built on 1
- simple_graph_hypercubeThe 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.
- Used by 3
- exists_hypercube_coilFor every n ≥ 2, there exists a coil in the hypercube Q_n.
- is_max_hypercube_coilA coil S in Q_n is a maximum coil if its cardinality is at least that of any other coil in Q_n.
- 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.
Read back from the Lean
Given a natural number n and a finite set S of vertices Fin n → Bool, hypercube_coil n S asserts that:
1. S contains at least 4 elements (4 ≤ S.card), and
2. There exists a graph isomorphism between the induced subgraph of the $n$-dimensional hypercube graph on S and the cycle graph on S.card vertices (SimpleGraph.cycleGraph S.card).
Here, the $n$-dimensional hypercube graph is defined on vertices Fin n → Bool with edges between pairs of vertices that differ at exactly one coordinate i : Fin n.
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
/-- A coil in the n-dimensional hypercube is an induced cycle of length at least 4. -/ def hypercube_coil (n : ℕ) (S : Finset (Fin n → Bool)) : Prop := 4 ≤ S.card ∧ Nonempty (((simple_graph_hypercube n).induce (S : Set (Fin n → Bool))) ≃g SimpleGraph.cycleGraph S.card)