AFTD Auto-Formalizing Theoretical Domains

hypercube_coil

def

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

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)
See it in the graphDiscuss this resultChallenge it