AFTD Auto-Formalizing Theoretical Domains

maxcut_deviation_degree_sum_ge

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 members of the coalition have total degree at least 2k|S|, so in particular some player of every deviating coalition has degree at least 2k.

Statement

theorem maxcut_deviation_degree_sum_ge {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 τ) :
    2 * k * S.card ≤ ∑ v ∈ S, G.degree v
Source
step towards maxcut_op89_optimal_strong_equilibrium_exists
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • maxcut_deviation_mono_inside_dropLet σ 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…
  • 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.
  • 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

Lean source view module on GitHub

/-- Any coalition that deviates strongly from an optimal k-colouring has total degree at least 2k|S|, i.e. average degree at least 2k. -/
theorem maxcut_deviation_degree_sum_ge {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 τ) :
    2 * k * S.card ≤ ∑ v ∈ S, G.degree v := by
  have hmono : ∀ v, k * (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card ≤ G.degree v := by
    intro v
    have hsum : (Finset.univ.filter fun w => G.Adj v w).card =
        ∑ c : Fin k, (Finset.univ.filter fun w => G.Adj v w ∧ σ w = c).card := by
      rw [Finset.card_eq_sum_card_fiberwise (f := σ) (t := Finset.univ)
        (fun _ _ => Finset.mem_coe.2 (Finset.mem_univ _))]
      simp only [Finset.filter_filter]
    have hdv : (Finset.univ.filter fun w => G.Adj v w).card = G.degree v := by
      rw [← SimpleGraph.card_neighborFinset_eq_degree, SimpleGraph.neighborFinset_eq_filter]
    have hlow : ∑ _c : Fin k, (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card ≤
        ∑ c : Fin k, (Finset.univ.filter fun w => G.Adj v w ∧ σ w = c).card :=
      Finset.sum_le_sum fun c _ => maxcut_optimal_same_color_le G σ hopt v c
    simp only [Finset.sum_const, Finset.card_univ, Fintype.card_fin, smul_eq_mul] at hlow
    omega
  have hdrop := maxcut_deviation_mono_inside_drop G σ τ S hopt hdev
  have hdrop' : 2 * S.card ≤ ∑ v ∈ S, ∑ w ∈ S, (if G.Adj v w ∧ σ w = σ v then 1 else 0 : ℕ) := by
    omega
  have hS_le : ∑ v ∈ S, ∑ w ∈ S, (if G.Adj v w ∧ σ w = σ v then 1 else 0 : ℕ) ≤
      ∑ v ∈ S, (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card := by
    refine Finset.sum_le_sum fun v _ => ?_
    calc ∑ w ∈ S, (if G.Adj v w ∧ σ w = σ v then 1 else 0 : ℕ)
        ≤ ∑ w ∈ Finset.univ, (if G.Adj v w ∧ σ w = σ v then 1 else 0 : ℕ) :=
          Finset.sum_le_sum_of_subset (Finset.subset_univ S)
      _ = (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card :=
          (Finset.card_filter _ _).symm
  calc 2 * k * S.card
      = k * (2 * S.card) := by ring
    _ ≤ k * (∑ v ∈ S, ∑ w ∈ S, (if G.Adj v w ∧ σ w = σ v then 1 else 0 : ℕ)) :=
        Nat.mul_le_mul_left k hdrop'
    _ ≤ k * ∑ v ∈ S, (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card :=
        Nat.mul_le_mul_left k hS_le
    _ = ∑ v ∈ S, k * (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card := by
        rw [Finset.mul_sum]
    _ ≤ ∑ v ∈ S, G.degree v :=
        Finset.sum_le_sum fun v _ => hmono v
See it in the graphDiscuss this resultChallenge it