AFTD Auto-Formalizing Theoretical Domains

is_maxcut_optimal

def

A coloring σ is optimal if no coloring τ : V → [k] has larger social welfare (equivalently, σ is a maximum k-cut).

Statement

def is_maxcut_optimal {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ : V → Fin k) : Prop
Defined in
arXiv:2610.04948 (Social Optimality Does Not Imply Coalitional Stability in Unweighted Max-k-Cut Games), Sec. 1
Verified
06 Oct 2026
Axioms
none listed
Built on 1
  • 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.
Used by 26

Lean source view module on GitHub

/-- An optimal coloring of the Max-k-Cut game: it maximizes social welfare (equivalently the cut value) over all colorings `V → Fin k`. -/
def is_maxcut_optimal {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ : V → Fin k) : Prop :=
  ∀ τ : V → Fin k, maxcut_welfare G τ ≤ maxcut_welfare G σ
See it in the graphDiscuss this resultChallenge it