ghz_vertex_colouring_weight
For any type V : Type* with [Fintype V], given a simple graph G on V, edge weights w : Sym2 V → ℂ, edge colouring c : Sym2 V → ℕ, and vertex colouring vc : V → ℕ, ghz_vertex_colouring_weight G w c vc is the sum of ghz_matching_weight w M over all M : Finset (Sym2 V) in Finset.univ such that ghz_is_perfect_matching G M holds and for all e in M and all v in V with v ∈ e, vc v = c e.
Statement
noncomputable def ghz_vertex_colouring_weight {V : Type*} [Fintype V] (G : SimpleGraph V) (w : Sym2 V → ℂ) (c : Sym2 V → ℕ) (vc : V → ℕ) : ℂ
- Defined in
- scout/2610-22190-connectivity-bounds-for-ghz-graphs.md:161
- Verified
- 21 Oct 2026
- Axioms
- none listed
- Built on 2
- ghz_is_perfect_matchingA set of edges M : Finset (Sym2 V) is a perfect matching in a simple graph G on a finite type V if every edge in M belongs to the edge set…
- ghz_matching_weightFor any type V : Type*, given an edge weight function w : Sym2 V → ℂ and a finite set of unordered pairs M : Finset (Sym2 V), the weight…
- Used by 1
- is_ghz_graphFor any type V : Type* with [Fintype V], a simple graph G on V with edge colouring c : Sym2 V → ℕ and edge weighting w : Sym2 V → ℂ…
Read back from the Lean
Given a finite type V, a simple graph G on V, an edge-weight function w : Sym2 V → ℂ, an edge-colouring c : Sym2 V → ℕ, and a vertex-colouring vc : V → ℕ, ghz_vertex_colouring_weight G w c vc is the complex number obtained by summing ∏ e ∈ M, w e over all M : Finset (Sym2 V) such that:
1. M is a perfect matching of G (every edge e ∈ M is an edge of G, and every vertex v : V belongs to exactly one e ∈ M), and
2. for every edge e ∈ M and every vertex v : V with v ∈ e, vc v = c e (both endpoints of each matching edge e have color c e).
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
/-- The weight of an inherited vertex colouring vc is the sum over all perfect matchings inducing vc of their weights. -/ noncomputable def ghz_vertex_colouring_weight {V : Type*} [Fintype V] (G : SimpleGraph V) (w : Sym2 V → ℂ) (c : Sym2 V → ℕ) (vc : V → ℕ) : ℂ := open scoped Classical in ∑ M ∈ Finset.univ.filter (fun M => ghz_is_perfect_matching G M ∧ ∀ e ∈ M, ∀ v : V, v ∈ e → vc v = c e), ghz_matching_weight w M