Fundamental cycles of a spanning tree generate all flows
Provedexists_fundamentalCycles_of_spanningTreeLet and be finite types with decidable equality, and let be two maps, to be read as the head and tail of each edge of a finite directed multigraph, so that runs from to . Let be a finite set of edges, and assume the spanning-tree hypothesis in the following form: for every pair of vertices there is exactly one supported on (that is, for all ) whose divergence at each vertex , namely , equals . The conclusion asserts the existence of such that: (i) for every index , the chain is a circulation, i.e. at every vertex ; (ii) for in the complement one has if and otherwise; (iii) for ; and (iv) for every additive commutative group and every satisfying the balance condition at every vertex , one has for every edge , the coefficients acting through the -module structure of .
This is the classical statement that the fundamental cycles attached to the edges outside a spanning tree span the cycle space of a finite directed multigraph, here formulated for flows with values in an arbitrary abelian group: such a flow is determined, with universal integer coefficients, by its values on the non-tree edges. It is used in the construction of path integrals on curves, in AlgebraicCurve.exists_loops_pathIntegral_reciprocity_raw and in CerednikDrinfeld.Omega.exists_isUnit_det_pathCycle_and_span_pathCycle.
import Mathlib set_option maxHeartbeats 4000000 set_option synthInstance.maxHeartbeats 400000 set_option backward.isDefEq.respectTransparency.types false
theorem exists_fundamentalCycles_of_spanningTree {V E : Type*} [Fintype V] [Fintype E]
[DecidableEq V] [DecidableEq E] (hd tl : E → V) (T : Finset E)
(hTpath : ∀ u v : V, ∃! c : E → ℤ, (∀ e ∉ T, c e = 0) ∧
∀ w, (∑ e with hd e = w, c e) - (∑ e with tl e = w, c e) =
(if w = v then 1 else 0) - (if w = u then 1 else 0)) :
∃ Z : E → E → ℤ,
(∀ j, ∀ w, (∑ e with hd e = w, Z j e) = (∑ e with tl e = w, Z j e)) ∧
(∀ j ∈ Tᶜ, ∀ j' ∈ Tᶜ, Z j j' = if j = j' then 1 else 0) ∧
(∀ j ∈ T, Z j = 0) ∧
∀ {A : Type*} [inst : AddCommGroup A] (f : E → A),
(∀ w, (∑ e with hd e = w, f e) = (∑ e with tl e = w, f e)) →
∀ e, f e = ∑ j ∈ Tᶜ, Z j e • f j := by sorry