maxcut_deviation_internal_color_count_lt
theoremverified
Let σ be an optimal colouring of the unweighted Max-k-Cut game on a finite simple graph G and let (S,τ) be a strong deviation from σ. Then every member v of the coalition ends up with strictly fewer coalition-neighbours of the colour it moves to than it had of that colour before: #{w ∈ S : v adjacent w and τ(w) = τ(v)} < #{w ∈ S : v adjacent w and σ(w) = τ(v)}.
Statement
theorem maxcut_deviation_internal_color_count_lt {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ τ : V → Fin k) (S : Finset V) (hopt : is_maxcut_optimal G σ) (hdev : is_maxcut_strong_deviation G σ S τ) {v : V} (hv : v ∈ S) : (S.filter fun w => G.Adj v w ∧ τ w = τ v).card < (S.filter fun w => G.Adj v w ∧ σ w = τ v).card
- Source
- step towards maxcut_op89_optimal_strong_equilibrium_exists
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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_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_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…
- is_maxcut_optimalA coloring σ is optimal if no coloring τ : V → [k] has larger social welfare (equivalently, σ is a maximum k-cut).
- Used by 1
- maxcut_op89_exists_of_card_le_two_mul_add_oneFor every integer k ≥ 3 and every finite simple graph G on at most 2k+1 vertices, the unweighted Max-k-Cut game on (G,k) admits an optimal…
Lean source view module on GitHub
/-- Each deviating player at an optimal colouring strictly reduces its count of coalition-neighbours of the colour it switches to. -/ theorem maxcut_deviation_internal_color_count_lt {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ τ : V → Fin k) (S : Finset V) (hopt : is_maxcut_optimal G σ) (hdev : is_maxcut_strong_deviation G σ S τ) {v : V} (hv : v ∈ S) : (S.filter fun w => G.Adj v w ∧ τ w = τ v).card < (S.filter fun w => G.Adj v w ∧ σ w = τ v).card := by have hu : maxcut_utility G σ v < maxcut_utility G τ v := hdev.2.2 v hv have hσ_deg := maxcut_utility_add_monochromatic_card G σ v have hτ_deg := maxcut_utility_add_monochromatic_card G τ v have h1 : (Finset.univ.filter fun w => G.Adj v w ∧ τ w = τ v).card < (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card := by omega have h2 : (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card ≤ (Finset.univ.filter fun w => G.Adj v w ∧ σ w = τ v).card := maxcut_optimal_same_color_le G σ hopt v (τ v) have hlt : (Finset.univ.filter fun w => G.Adj v w ∧ τ w = τ v).card < (Finset.univ.filter fun w => G.Adj v w ∧ σ w = τ v).card := lt_of_lt_of_le h1 h2 have hsplit_τ : (Finset.filter (· ∈ S) (Finset.univ.filter (fun w => G.Adj v w ∧ τ w = τ v))).card + (Finset.filter (· ∉ S) (Finset.univ.filter (fun w => G.Adj v w ∧ τ w = τ v))).card = (Finset.univ.filter (fun w => G.Adj v w ∧ τ w = τ v)).card := Finset.card_filter_add_card_filter_not (s := Finset.univ.filter (fun w => G.Adj v w ∧ τ w = τ v)) (· ∈ S) have hsplit_σ : (Finset.filter (· ∈ S) (Finset.univ.filter (fun w => G.Adj v w ∧ σ w = τ v))).card + (Finset.filter (· ∉ S) (Finset.univ.filter (fun w => G.Adj v w ∧ σ w = τ v))).card = (Finset.univ.filter (fun w => G.Adj v w ∧ σ w = τ v)).card := Finset.card_filter_add_card_filter_not (s := Finset.univ.filter (fun w => G.Adj v w ∧ σ w = τ v)) (· ∈ S) have hS_τ : Finset.filter (· ∈ S) (Finset.univ.filter (fun w => G.Adj v w ∧ τ w = τ v)) = Finset.filter (fun w => G.Adj v w ∧ τ w = τ v) S := by ext w; simp [and_comm] have hS_σ : Finset.filter (· ∈ S) (Finset.univ.filter (fun w => G.Adj v w ∧ σ w = τ v)) = Finset.filter (fun w => G.Adj v w ∧ σ w = τ v) S := by ext w; simp [and_comm] have h_out : Finset.filter (· ∉ S) (Finset.univ.filter (fun w => G.Adj v w ∧ τ w = τ v)) = Finset.filter (· ∉ S) (Finset.univ.filter (fun w => G.Adj v w ∧ σ w = τ v)) := by ext w simp only [Finset.mem_filter, Finset.mem_univ, true_and] constructor · rintro ⟨⟨hadj, hτ_w⟩, hw⟩ rw [hdev.2.1 w hw] at hτ_w exact ⟨⟨hadj, hτ_w⟩, hw⟩ · rintro ⟨⟨hadj, hσ_w⟩, hw⟩ rw [← hdev.2.1 w hw] at hσ_w exact ⟨⟨hadj, hσ_w⟩, hw⟩ rw [hS_τ] at hsplit_τ rw [hS_σ] at hsplit_σ rw [h_out] at hsplit_τ omega