ghz_matching_index
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) } }