maxcut_deviation_cross_mono_rise
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 the deviation creates at least |S| new ordered monochromatic pairs crossing the coalition boundary: with X(ρ) = Σ_{v∈S} Σ_{w∉S} [v adjacent w and ρ(w) = ρ(v)], one has X(σ) + |S| ≤ X(τ).
Statement
theorem maxcut_deviation_cross_mono_rise {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 ∈ S, ∑ w ∈ Sᶜ, (if G.Adj v w ∧ σ w = σ v then 1 else 0 : ℕ)) + S.card ≤ ∑ v ∈ S, ∑ w ∈ Sᶜ, (if G.Adj v w ∧ τ w = τ v then 1 else 0 : ℕ)
- Source
- step towards maxcut_op89_optimal_strong_equilibrium_exists
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- maxcut_welfare_splitFor any set S of players, the welfare of a coloring is A + 2B + C, where A counts bichromatic adjacent ordered pairs inside S, B those…
- maxcut_utility_sum_splitFor any set S, the total utility of the members of S is A + B, with A the bichromatic adjacent ordered pairs inside S and B those from S…
- 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…
- maxcut_welfareThe social welfare of a coloring σ in the Max-k-Cut game: the sum over all players v of u_v(σ), equal to twice the cut value.
- is_maxcut_optimalA coloring σ is optimal if no coloring τ : V → [k] has larger social welfare (equivalently, σ is a maximum k-cut).
Lean source view module on GitHub
/-- A strong deviation from an optimal colouring increases the ordered monochromatic pairs across the coalition boundary by at least |S|. -/ theorem maxcut_deviation_cross_mono_rise {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 ∈ S, ∑ w ∈ Sᶜ, (if G.Adj v w ∧ σ w = σ v then 1 else 0 : ℕ)) + S.card ≤ ∑ v ∈ S, ∑ w ∈ Sᶜ, (if G.Adj v w ∧ τ w = τ v then 1 else 0 : ℕ) := by obtain ⟨hne, hout, hgain⟩ := hdev have hgains : ∑ v ∈ S, maxcut_utility G σ v + S.card ≤ ∑ v ∈ S, maxcut_utility G τ v := by have := Finset.sum_le_sum fun v hv => Nat.succ_le_of_lt (hgain v hv) simpa [Finset.sum_add_distrib] using this have hu_σ := maxcut_utility_sum_split G σ S have hu_τ := maxcut_utility_sum_split G τ S have hw_σ := maxcut_welfare_split G σ S have hw_τ := maxcut_welfare_split G τ S have hop := hopt τ have hC : (∑ v ∈ Sᶜ, ∑ w ∈ Sᶜ, (if G.Adj v w ∧ τ w ≠ τ v then 1 else 0 : ℕ)) = ∑ v ∈ Sᶜ, ∑ w ∈ Sᶜ, (if G.Adj v w ∧ σ w ≠ σ v then 1 else 0 : ℕ) := by refine Finset.sum_congr rfl fun v hv => Finset.sum_congr rfl fun w hw => ?_ rw [Finset.mem_compl] at hv hw rw [hout v hv, hout w hw] have hX (ρ : V → Fin k) : (∑ v ∈ S, ∑ w ∈ Sᶜ, (if G.Adj v w ∧ ρ w = ρ v then 1 else 0 : ℕ)) + (∑ v ∈ S, ∑ w ∈ Sᶜ, (if G.Adj v w ∧ ρ w ≠ ρ v then 1 else 0 : ℕ)) = ∑ v ∈ S, ∑ w ∈ Sᶜ, (if G.Adj v w then 1 else 0 : ℕ) := by rw [← Finset.sum_add_distrib] refine Finset.sum_congr rfl fun v hv => ?_ rw [← Finset.sum_add_distrib] refine Finset.sum_congr rfl fun w hw => ?_ by_cases h : G.Adj v w · by_cases heq : ρ w = ρ v · simp [h, heq] · simp [h, heq] · simp [h] have hX_σ := hX σ have hX_τ := hX τ omega