AFTD Auto-Formalizing Theoretical Domains

is_hypercube_square

def

A subset of 4 vertices in the hypercube Q_n is a square if its induced subgraph is isomorphic to the 4-cycle C_4.

Statement

def is_hypercube_square (n : ℕ) (sq : Finset (Fin n → Bool)) : Prop
Defined in
arXiv:2610.36461 Section 2.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 2

Read back from the Lean

is_hypercube_square n sq asserts that the finite set sq of vertices of the $n$-dimensional hypercube (functions Fin n → Bool) has cardinality 4, and that the subgraph of the $n$-hypercube graph induced by sq is isomorphic (as a simple graph) to the 4-cycle graph SimpleGraph.cycleGraph 4.

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 square in Q_n is a 4-vertex subset inducing a 4-cycle. -/
def is_hypercube_square (n : ℕ) (sq : Finset (Fin n → Bool)) : Prop :=
  sq.card = 4 ∧ Nonempty (((simple_graph_hypercube n).induce (sq : Set (Fin n → Bool))) ≃g SimpleGraph.cycleGraph 4)
See it in the graphDiscuss this resultChallenge it