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
- maxcut_optimal_not_strong_degree_66There is a finite simple graph of maximum degree at most 66 with an optimal coloring of the Max-3-Cut game that is not a strong…
- maxcut_optimal_strong_of_degree_leFor every k ≥ 1: on every finite simple graph whose maximum degree is at most 2k − 1, every optimal coloring of the unweighted Max-k-Cut…
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 σ