AFTD Auto-Formalizing Theoretical Domains

is_maxcut_neutral_pivot_safe

def

No coalition can move the designated pivot while weakly improving its utility and strictly improving every other coalition member.

Statement

def is_maxcut_neutral_pivot_safe {V : Type} [Fintype V]
    (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ : V → Fin k) (u : V) : Prop
Source
Filed by the prover as a step towards another result
Verified
05 Nov 2026
Axioms
none listed
Built on 1
  • maxcut_utilityIn 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)…
Used by 2

Lean source view module on GitHub

def is_maxcut_neutral_pivot_safe {V : Type} [Fintype V]
    (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ : V → Fin k) (u : V) : Prop := ∀ (C : Finset V) (τ : V → Fin k),
      u ∈ C → τ u ≠ σ u → (∀ x, x ∉ C → τ x = σ x) →
      maxcut_utility G σ u ≤ maxcut_utility G τ u →
      (∀ x ∈ C, x ≠ u → maxcut_utility G σ x < maxcut_utility G τ x) → False
See it in the graphDiscuss this resultChallenge it