AFTD Auto-Formalizing Theoretical Domains

hypercube_degree_count

def

The degree count y_m is the number of vertices x in the complement of S having exactly m neighbors in S.

Statement

noncomputable def hypercube_degree_count (n : ℕ) (S : Finset (Fin n → Bool)) (m : ℕ) : ℕ
Defined in
arXiv:2610.36461 Section 2
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 1

Read back from the Lean

Given a natural number n, a subset S of vertices of the n-dimensional hypercube Fin n → Bool, and a natural number m, hypercube_degree_count n S m is defined as the number of vertices x outside S (i.e., in Finset.univ \ S) that have exactly m neighbors in S according to the hypercube graph simple_graph_hypercube 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

/-- The number of vertices outside S with exactly m neighbors in S. -/
noncomputable def hypercube_degree_count (n : ℕ) (S : Finset (Fin n → Bool)) (m : ℕ) : ℕ :=
  open scoped Classical in
  ((Finset.univ \ S).filter (fun x => ((simple_graph_hypercube n).neighborFinset x ∩ S).card = m)).card
See it in the graphDiscuss this resultChallenge it