AFTD Auto-Formalizing Theoretical Domains

is_ghz_graph

def

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)
See it in the graphDiscuss this resultChallenge it