AFTD Auto-Formalizing Theoretical Domains

maxcut_has_optimal_strong_equilibrium

def

In the unweighted Max-k-Cut game on a finite simple graph G with k colors, there exists an optimal coloring σ : V → Fin k that is also a strong equilibrium.

Statement

def maxcut_has_optimal_strong_equilibrium {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (k : ℕ) : Prop
Defined in
arXiv:2610.04948 Sec. 4
Verified
25 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 11

Read back from the Lean

For a finite type V, a simple graph G on V with decidable adjacency relation, and a natural number k, this defines the proposition that there exists an assignment σ : V → Fin k such that: 1. (is_maxcut_optimal G σ): For every assignment τ : V → Fin k, the welfare of τ is less than or equal to the welfare of σ, where the welfare of an assignment is the sum over all v : V of maxcut_utility G · v (the number of neighbors w of v in G with different assignments); 2. (is_maxcut_strong_equilibrium G σ): For every finite subset S of V and every assignment τ : V → Fin k, it is not the case that S is non-empty, τ agrees with σ outside S (i.e., ∀ v, v ∉ S → τ v = σ v), and every vertex v ∈ S strictly improves its utility (i.e., maxcut_utility G σ v < maxcut_utility G τ v).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- A finite simple graph G admits an optimal coloring that is a strong equilibrium in the unweighted Max-k-Cut game. -/
def maxcut_has_optimal_strong_equilibrium {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (k : ℕ) : Prop := ∃ σ : V → Fin k, is_maxcut_optimal G σ ∧ is_maxcut_strong_equilibrium G σ
See it in the graphDiscuss this resultChallenge it