op_1695_bipartite_graph_fortuin_kasteleyn
For every bipartite simple graph G = (V, E), the bipartite subgraph polynomial bipartite_subgraph_magic_poly G equals 8^{-|V|} times the Fortuin-Kasteleyn polynomial fortuin_kasteleyn_poly G 8 (-2).
Statement
theorem op_1695_bipartite_graph_fortuin_kasteleyn {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.IsBipartite) : bipartite_subgraph_magic_poly G = (1 / (8 ^ Fintype.card V : ℝ)) * fortuin_kasteleyn_poly G 8 (-2)
- Formalizes
- OP-1695
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- bipartite_subgraph_magic_polyFor a finite simple graph G = (V, E), the bipartite subgraph magic polynomial is 8^{-|V|} times the sum over all edge subsets A ⊆ E such…
- fortuin_kasteleyn_polyFor 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…
Read back from the Lean
For any finite type $V$ with decidable equality, and any simple graph $G$ on $V$ with decidable adjacency, if $G$ is bipartite (G.IsBipartite), then the bipartite subgraph polynomial of $G$ (bipartite_subgraph_magic_poly G) is equal to $8^{-|V|}$ times the Fortuin–Kasteleyn polynomial of $G$ evaluated at parameters $q = 8$ and $w = -2$ ((1 / (8 ^ Fintype.card V : ℝ)) * fortuin_kasteleyn_poly G 8 (-2)).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
Every subgraph of a bipartite graph is itself bipartite, as it inherits the 2-coloring of the parent graph. Expanding the definition of the bipartite subgraph magic polynomial reveals a sum over all edge subsets of an indicator for bipartiteness times the Fortuin-Kasteleyn summand (-2)^{|A|} 8^{c(A)}, scaled by 8^{-|V|}. Because G is bipartite, every edge subset induces a bipartite subgraph, so the indicator is always true and the sum identically matches the Fortuin-Kasteleyn polynomial Z_G(8, -2).
The graph G admits a 2-coloring, and the edge set A is a subset of the edge set of G.
Because G is bipartite, it admits a proper 2-coloring c : V → Fin 2. Furthermore, coercing the inclusion of finite edge sets A ⊆ G.edgeFinset shows that every edge in A belongs to the edge set of G.
uses
SimpleGraph.mem_edgeFinset.mp,Finset.mem_coe.mpobtain ⟨c⟩ := hG have hsub : (↑A : Set (Sym2 V)) ⊆ G.edgeSet := by intro e he exact SimpleGraph.mem_edgeFinset.mp (hA (Finset.mem_coe.mp he))
The graph spanned by the edge set A is a subgraph of G.
By SimpleGraph.fromEdgeSet_le, a graph generated from an edge set is a subgraph of G if and only if all of its non-loop edges belong to G. Since every edge in A is an edge of G, the edge-induced subgraph is a subgraph of G.
uses
SimpleGraph.fromEdgeSet_lehave hle : SimpleGraph.fromEdgeSet (↑A : Set (Sym2 V)) ≤ G := by rw [SimpleGraph.fromEdgeSet_le] exact fun e he => hsub he.1
The subgraph formed by the edge set A is bipartite.
Vertices adjacent in the subgraph generated by A are also adjacent in G, so they receive distinct colors under the coloring c of G. Hence c provides a valid 2-coloring for the subgraph, showing it is bipartite.
refine ⟨⟨c.toFun, ?_⟩⟩ intro a b hadj exact c.map_rel' (hle hadj)
It suffices to show that the sum over edge subsets in the bipartite subgraph magic polynomial equals that in the Fortuin-Kasteleyn polynomial Z_G(8, -2).
Unfolding the definitions of bipartite_subgraph_magic_poly and fortuin_kasteleyn_poly reveals that both sides share the common prefactor 8^{-|V|}. Cancelling this prefactor reduces the identity to proving that the two sums over the powerset of edges are equal.
rw [bipartite_subgraph_magic_poly, fortuin_kasteleyn_poly] congr 1
The two sums are equal term-by-term because every edge-induced subgraph is bipartite.
Comparing the sums term-by-term using Finset.sum_congr, each edge subset A ⊆ E(G) spans a bipartite subgraph by the helper lemma op_1695_bipartite_graph_fortuin_kasteleyn_from_edge_set_is_bipartite. Thus if_pos simplifies the indicator condition to its positive branch, matching the summand (-2)^{|A|} 8^{c(A)} of the Fortuin-Kasteleyn polynomial.
uses
Finset.sum_congr,if_pos,op_1695_bipartite_graph_fortuin_kasteleyn_from_edge_set_is_bipartite,Finset.mem_powerset.mpapply Finset.sum_congr rfl intro A hA rw [if_pos (op_1695_bipartite_graph_fortuin_kasteleyn_from_edge_set_is_bipartite G hG A (Finset.mem_powerset.mp hA))]
SimpleGraph.mem_edgeFinset.mp- An edge of a graph belongs to its edge set if it belongs to its finite edge set.
Finset.mem_coe.mp- An element belongs to a finite set if it belongs to the set obtained by coercing that finite set.
SimpleGraph.fromEdgeSet_le- The simple graph formed by an edge set s is a subgraph of G if and only if every non-loop pair in s is an edge of G.
Finset.sum_congr- Two finite sums are equal if their index sets are equal and their summands agree on every element of the index set.
if_pos- A conditional expression `if c then t else e` equals t whenever c is true.
op_1695_bipartite_graph_fortuin_kasteleyn_from_edge_set_is_bipartite- Any simple graph formed by a subset of the edges of a bipartite graph is itself bipartite.
Finset.mem_powerset.mp- A finite set belongs to the powerset of s if and only if it is a subset of s.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
private lemma op_1695_bipartite_graph_fortuin_kasteleyn_from_edge_set_is_bipartite {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.IsBipartite) (A : Finset (Sym2 V)) (hA : A ⊆ G.edgeFinset) : (SimpleGraph.fromEdgeSet (↑A : Set (Sym2 V))).IsBipartite := by obtain ⟨c⟩ := hG have hsub : (↑A : Set (Sym2 V)) ⊆ G.edgeSet := by intro e he exact SimpleGraph.mem_edgeFinset.mp (hA (Finset.mem_coe.mp he)) have hle : SimpleGraph.fromEdgeSet (↑A : Set (Sym2 V)) ≤ G := by rw [SimpleGraph.fromEdgeSet_le] exact fun e he => hsub he.1 refine ⟨⟨c.toFun, ?_⟩⟩ intro a b hadj exact c.map_rel' (hle hadj)/-- For a bipartite graph, the bipartite subgraph magic polynomial equals 8^{-|V|} Z_G(8, -2). -/theorem op_1695_bipartite_graph_fortuin_kasteleyn {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.IsBipartite) : bipartite_subgraph_magic_poly G = (1 / (8 ^ Fintype.card V : ℝ)) * fortuin_kasteleyn_poly G 8 (-2) := by rw [bipartite_subgraph_magic_poly, fortuin_kasteleyn_poly] congr 1 apply Finset.sum_congr rfl intro A hA rw [if_pos (op_1695_bipartite_graph_fortuin_kasteleyn_from_edge_set_is_bipartite G hG A (Finset.mem_powerset.mp hA))]