maxcut_optimal_strong_of_color_unused
theoremverified
If σ is an optimal colouring of the unweighted Max-k-Cut game on a finite simple graph G and some colour c is never used by σ, then σ is a strong equilibrium.
Statement
theorem maxcut_optimal_strong_of_color_unused {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (hk : 0 < k) (σ : V → Fin k) (c : Fin k) (hc : ∀ v, σ v ≠ c) (hopt : is_maxcut_optimal G σ) : is_maxcut_strong_equilibrium G σ
- Source
- step towards maxcut_op89_optimal_strong_equilibrium_exists
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- maxcut_optimal_same_color_leAt an optimal coloring σ of the Max-k-Cut game, for every vertex v and every color c, the number of neighbours of v with color σ(v) is at…
- maxcut_utility_add_monochromatic_cardA player's utility plus the number of its neighbours sharing its colour equals its degree.
- maxcut_utility_le_degreeA player's utility in the Max-k-Cut game never exceeds its degree: the neighbours cut away by v form a subset of the neighbours of v.
- is_maxcut_strong_equilibriumA coloring σ is a strong equilibrium of the Max-k-Cut game if no coalition has a strong deviation from it.
- maxcut_utilityIn the unweighted Max-k-Cut game on a finite simple graph G, a coloring σ : V → [k] gives player v the utility u_v(σ) = |{w ∈ N(v) : σ(w)…
- is_maxcut_optimalA coloring σ is optimal if no coloring τ : V → [k] has larger social welfare (equivalently, σ is a maximum k-cut).
- is_maxcut_strong_deviationA strong deviation from σ is a nonempty coalition S ⊆ V with a coloring τ agreeing with σ outside S such that u_v(τ) > u_v(σ) for every v…
Lean source view module on GitHub
/-- An optimal colouring that leaves a colour unused is automatically a strong equilibrium. -/ theorem maxcut_optimal_strong_of_color_unused {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (hk : 0 < k) (σ : V → Fin k) (c : Fin k) (hc : ∀ v, σ v ≠ c) (hopt : is_maxcut_optimal G σ) : is_maxcut_strong_equilibrium G σ := by intro S τ hdev rcases hdev with ⟨hne, -, hstrict⟩ obtain ⟨v, hv⟩ := hne have h_c_empty : (Finset.univ.filter fun w => G.Adj v w ∧ σ w = c) = ∅ := by rw [Finset.filter_eq_empty_iff] intro w _ hw exact hc w hw.2 have h_same_le := maxcut_optimal_same_color_le G σ hopt v c rw [h_c_empty, Finset.card_empty] at h_same_le have h_add := maxcut_utility_add_monochromatic_card G σ v have h_tau_le := maxcut_utility_le_degree G τ v have hlt := hstrict v hv omega