AFTD Auto-Formalizing Theoretical Domains

maxcut_optimal_strong_up_to_degree

def

For k and D: on every finite simple graph of maximum degree at most D, every optimal coloring of the Max-k-Cut game with k colors is a strong equilibrium.

Statement

def maxcut_optimal_strong_up_to_degree (k D : ℕ) : Prop
Defined in
arXiv:2610.04948 (Social Optimality Does Not Imply Coalitional Stability in Unweighted Max-k-Cut Games), after Corollary 9 (the degree threshold the open question asks about)
Verified
06 Oct 2026
Axioms
none listed
Built on 2
  • is_maxcut_optimalA coloring σ is optimal if no coloring τ : V → [k] has larger social welfare (equivalently, σ is a maximum k-cut).
  • is_maxcut_strong_equilibriumA coloring σ is a strong equilibrium of the Max-k-Cut game if no coalition has a strong deviation from it.
Used by 2

Lean source view module on GitHub

/-- Every optimal coloring is stable up to degree `D`: on every finite simple graph whose vertex degrees are all at most `D`, every optimal coloring of the Max-k-Cut game is a strong equilibrium. The threshold Δ*(k) of the open problem is the largest such `D`. -/
def maxcut_optimal_strong_up_to_degree (k D : ℕ) : Prop :=
  ∀ (V : Type) [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj],
    (∀ v, G.degree v ≤ D) →
      ∀ σ : V → Fin k, is_maxcut_optimal G σ → is_maxcut_strong_equilibrium G σ
See it in the graphDiscuss this resultChallenge it