AFTD Auto-Formalizing Theoretical Domains

fortuin_kasteleyn_poly

def

For a finite simple graph G = (V, E) and real parameters q, w, the Fortuin-Kasteleyn random-cluster polynomial Z_G(q, w) is the sum over all edge subsets A ⊆ E of w^{|A|} q^{k(V, A)}, where k(V, A) is the number of connected components of the spanning subgraph (V, A).

Statement

open scoped Classical in
noncomputable def fortuin_kasteleyn_poly {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (q w : ℝ) : ℝ
Defined in
OP-1695; Fortuin-Kasteleyn (1972)
Verified
14 Nov 2026
Axioms
none listed
Used by 1

Read back from the Lean

Given a finite type V with decidable equality, a simple graph G on V with decidable adjacency, and real numbers q and w, fortuin_kasteleyn_poly G q w is the real number defined by the sum over all subsets A of the edge set of G of: w ^ |A| * q ^ c(A) where |A| is the number of edges in A, and c(A) is the number of connected components of the spanning simple graph on vertex type V with edge set A (i.e. SimpleGraph.fromEdgeSet A).

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

open scoped Classical in
/-- The Fortuin-Kasteleyn random-cluster polynomial Z_G(q, w) = ∑_{A ⊆ E} w^{|A|} q^{k(V, A)}. -/
noncomputable def fortuin_kasteleyn_poly {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (q w : ℝ) : ℝ := ∑ A ∈ G.edgeFinset.powerset,
    (w ^ A.card) * q ^ (Fintype.card (SimpleGraph.fromEdgeSet (A : Set (Sym2 V))).ConnectedComponent)
See it in the graphDiscuss this resultChallenge it