AFTD Auto-Formalizing Theoretical Domains

maxcut_optimal_strong_of_internal_mono_lt

theoremverified

If σ 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 fewer than 2|S| ordered monochromatic adjacent pairs under σ (that is Σ_{v∈S} Σ_{w∈S} [v adjacent w and σ(w) = σ(v)] < 2|S|), then σ is a strong equilibrium.

Statement

theorem maxcut_optimal_strong_of_internal_mono_lt {V : Type} [Fintype V]
    (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ : V → Fin k)
    (hopt : is_maxcut_optimal G σ)
    (hS : ∀ S : Finset V, S.Nonempty →
      (∑ v ∈ S, ∑ w ∈ S, (if G.Adj v w ∧ σ w = σ v then 1 else 0 : ℕ)) < 2 * S.card) :
    is_maxcut_strong_equilibrium G σ
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…
  • is_maxcut_optimalA coloring σ is optimal if no coloring τ : V → [k] has larger social welfare (equivalently, σ is a maximum k-cut).
  • 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_strong_equilibriumA coloring σ is a strong equilibrium of the Max-k-Cut game if no coalition has a strong deviation from it.

Lean source view module on GitHub

/-- An optimal colouring whose every nonempty vertex set carries fewer than 2|S| ordered monochromatic internal pairs is a strong equilibrium. -/
theorem maxcut_optimal_strong_of_internal_mono_lt {V : Type} [Fintype V]
    (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ : V → Fin k)
    (hopt : is_maxcut_optimal G σ)
    (hS : ∀ S : Finset V, S.Nonempty →
      (∑ v ∈ S, ∑ w ∈ S, (if G.Adj v w ∧ σ w = σ v then 1 else 0 : ℕ)) < 2 * S.card) :
    is_maxcut_strong_equilibrium G σ := by
  classical
  intro S τ hdev
  have hdrop := maxcut_deviation_mono_inside_drop G σ τ S hopt hdev
  have hlt := hS S hdev.1
  have hnonneg : (0:ℕ) ≤ ∑ v ∈ S, ∑ w ∈ S, (if G.Adj v w ∧ τ w = τ v then 1 else 0 : ℕ) :=
    Nat.zero_le _
  omega
See it in the graphDiscuss this resultChallenge it