fortuin_kasteleyn_poly
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
- op_1695_bipartite_graph_fortuin_kasteleynFor every bipartite simple graph G = (V, E), the bipartite subgraph polynomial bipartite_subgraph_magic_poly G equals 8^{-|V|} times the…
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)