bipartite_subgraph_magic_poly
For 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 that (V, A) is bipartite of (-2)^{|A|} 8^{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 bipartite_subgraph_magic_poly {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] : ℝ
- Defined in
- OP-1695
- 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 and a simple graph $G$ on $V$ with decidable adjacency, bipartite_subgraph_magic_poly G is the real number defined by:
$$\frac{1}{8^{|V|}} \sum_{A \subseteq E(G)} \begin{cases} (-2)^{|A|} \cdot 8^{c(V, A)} & \text{if the spanning subgraph } (V, A) \text{ is bipartite} \\ 0 & \text{otherwise} \end{cases}$$
where:
- $|V|$ is the number of vertices (Fintype.card V),
- $E(G)$ is the finite edge set of $G$ (G.edgeFinset),
- the sum is taken over all subsets $A \subseteq E(G)$ (G.edgeFinset.powerset),
- $(V, A)$ is the spanning subgraph of $V$ with edge set $A$ (SimpleGraph.fromEdgeSet (A : Set (Sym2 V))),
- $|A|$ is the number of edges in $A$ (A.card),
- $c(V, A)$ is the number of connected components of $(V, A)$ (Fintype.card (SimpleGraph.fromEdgeSet A).ConnectedComponent), and
- the subgraph is tested for bipartiteness using SimpleGraph.IsBipartite.
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 bipartite subgraph polynomial 8^{-|V|} ∑_{A ⊆ E, (V,A) bipartite} (-2)^{|A|} 8^{k(V,A)}. -/ noncomputable def bipartite_subgraph_magic_poly {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] : ℝ := (1 / (8 ^ Fintype.card V : ℝ)) * ∑ A ∈ G.edgeFinset.powerset, if (SimpleGraph.fromEdgeSet (A : Set (Sym2 V))).IsBipartite then ((-2 : ℝ) ^ A.card) * (8 : ℝ) ^ (Fintype.card (SimpleGraph.fromEdgeSet (A : Set (Sym2 V))).ConnectedComponent) else 0