AFTD Auto-Formalizing Theoretical Domains

maxcut_utility

def

In 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) ≠ σ(v)}|.

Statement

def maxcut_utility {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ : V → Fin k) (v : V) : ℕ
Defined in
arXiv:2610.04948 (Social Optimality Does Not Imply Coalitional Stability in Unweighted Max-k-Cut Games), Sec. 1 (definition of the game and utilities)
Verified
06 Oct 2026
Axioms
none listed
Used by 53

Lean source view module on GitHub

/-- Utility of player `v` in the unweighted Max-k-Cut game on `G` under the coloring `σ`: the number of neighbours of `v` whose color differs from `v`'s. -/
def maxcut_utility {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ : V → Fin k) (v : V) : ℕ :=
  (Finset.univ.filter fun w => G.Adj v w ∧ σ w ≠ σ v).card
See it in the graphDiscuss this resultChallenge it