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
- maxcut_neutral_pivot_safe_not_necessaryA full graph and its vertex deletion may both be strongly stable, with exactly one restored-vertex conflict, while that conflict neighbor…
- maxcut_unused_color_or_safe_pivot_of_proper_coloringIf a finite graph admits a proper k-coloring and N has fewer than 2k vertices, there is a strong equilibrium with an unused color on N or…
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