maxcut_deviation_mono_inside_drop
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 number of ordered monochromatic adjacent pairs inside S drops by at least 2|S|: with M(ρ) = Σ_{v∈S} Σ_{w∈S} [v adjacent w and ρ(w) = ρ(v)], one has M(τ) + 2|S| ≤ M(σ). Halving, this is arXiv:2610.04948, Theorem 8: a deviating coalition from an optimal colouring removes at least |S| monochromatic edges inside itself.
Statement
theorem maxcut_deviation_mono_inside_drop {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 : ℕ)) + 2 * 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_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_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_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).
- Used by 3
- 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…
- maxcut_optimal_strong_of_internal_mono_ltIf σ is an optimal colouring of the unweighted Max-k-Cut game on a finite simple graph G and every nonempty set S of vertices carries…
- maxcut_deviation_degree_sum_geLet σ 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…
Lean source view module on GitHub
/-- A strong deviation from an optimal colouring destroys at least 2|S| ordered monochromatic pairs inside the coalition. -/ theorem maxcut_deviation_mono_inside_drop {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 : ℕ)) + 2 * 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 hM (ρ : 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 hM_σ := hM σ have hM_τ := hM τ omega