is_ghz_graph
For 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 → ℂ satisfies is_ghz_graph G c w if every edge e in G.edgeSet has w e ≠ 0, every feasible monochromatic vertex colouring has ghz_vertex_colouring_weight G w c vc = 1 (where feasible means there exists M : Finset (Sym2 V) satisfying ghz_is_perfect_matching G M and ∀ e ∈ M, ∀ v : V, v ∈ e → vc v = c e, and monochromatic means ∃ k : ℕ, ∀ v : V, vc v = k), and every non-monochromatic vertex colouring vc : V → ℕ (satisfying ¬ ∃ k : ℕ, ∀ v : V, vc v = k) has ghz_vertex_colouring_weight G w c vc = 0.
Statement
def is_ghz_graph {V : Type*} [Fintype V] (G : SimpleGraph V) (c : Sym2 V → ℕ) (w : Sym2 V → ℂ) : Prop
- Defined in
- scout/2610-22190-connectivity-bounds-for-ghz-graphs.md:167
- 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_vertex_colouring_weightFor 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…
- Used by 2
- ghz_matching_index_le_min_degreeFor any finite type V with decidable equality and any connected simple graph G on V with decidable adjacency, the matching index…
- ghz_matching_indexFor any type V : Type* with [Fintype V], the matching index ghz_matching_index G of a simple graph G on V is the supremum (sSup in ℕ) of…
Read back from the Lean
Given a finite type V, a simple graph G on V, an edge coloring c : Sym2 V → ℕ, and a complex edge weighting w : Sym2 V → ℂ, is_ghz_graph G c w asserts the conjunction of three conditions:
1. **Non-zero weights on edges:** For every edge e ∈ G.edgeSet, w e ≠ 0.
2. **Weight 1 on realizable monochromatic colorings:** For every vertex coloring vc : V → ℕ, IF:
- there exists a finset M : Finset (Sym2 V) that is a perfect matching of G such that for every edge e ∈ M and every vertex v ∈ e, vc v = c e, AND
- vc is constant (i.e., ∃ k : ℕ, ∀ v : V, vc v = k),
THEN ghz_vertex_colouring_weight G w c vc = 1.
3. **Weight 0 on non-monochromatic colorings:** For every vertex coloring vc : V → ℕ, IF vc is not constant (i.e., ¬ ∃ k : ℕ, ∀ v : V, vc v = k), THEN ghz_vertex_colouring_weight G w c vc = 0.
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
/-- An edge-coloured and weighted simple graph is a GHZ graph if all monochromatic feasible colourings have weight 1 and all non-monochromatic colourings have weight 0. -/ def is_ghz_graph {V : Type*} [Fintype V] (G : SimpleGraph V) (c : Sym2 V → ℕ) (w : Sym2 V → ℂ) : Prop := (∀ e ∈ G.edgeSet, w e ≠ 0) ∧ (∀ vc : V → ℕ, (∃ M : Finset (Sym2 V), ghz_is_perfect_matching G M ∧ (∀ e ∈ M, ∀ v : V, v ∈ e → vc v = c e)) → (∃ k : ℕ, ∀ v : V, vc v = k) → ghz_vertex_colouring_weight G w c vc = 1) ∧ (∀ vc : V → ℕ, ¬ (∃ k : ℕ, ∀ v : V, vc v = k) → ghz_vertex_colouring_weight G w c vc = 0)