AFTD Auto-Formalizing Theoretical Domains

ghz_matching_index

def

For 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 the set of natural numbers d : ℕ for which there exist an edge colouring c : Sym2 V → ℕ and edge weights w : Sym2 V → ℂ such that is_ghz_graph G c w holds, where d = Set.ncard { 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 }.

Statement

noncomputable def ghz_matching_index {V : Type*} [Fintype V] (G : SimpleGraph V) : ℕ
Defined in
scout/2610-22190-connectivity-bounds-for-ghz-graphs.md:191
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…
  • 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 → ℂ…
Used by 1
  • 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…

Read back from the Lean

Given a finite type V and a simple graph G on V, ghz_matching_index G is defined as the supremum (sSup in ℕ) of the set of natural numbers d such that there exist an edge coloring c : Sym2 V → ℕ and a complex edge weighting w : Sym2 V → ℂ satisfying: 1. G, c, and w form a GHZ graph (is_ghz_graph G c w); and 2. d equals the cardinality (Set.ncard) of the set of vertex colorings vc : V → ℕ that are both: - compatible with some perfect matching M of G (there exists a finset M of edges such that M is a perfect matching of G and for all e ∈ M and v ∈ e, vc v = c e), and - constant / monochromatic (there exists k : ℕ such that for all v : V, vc v = k).

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 matching index μ(G) is the supremum over all GHZ colourings and weightings of the number of feasible monochromatic inherited vertex colourings. -/
noncomputable def ghz_matching_index {V : Type*} [Fintype V] (G : SimpleGraph V) : ℕ := open scoped Classical in
  sSup { d : ℕ | ∃ (c : Sym2 V → ℕ) (w : Sym2 V → ℂ),
    is_ghz_graph G c w ∧
    d = Set.ncard { 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) } }
See it in the graphDiscuss this resultChallenge it