maxcut_has_optimal_strong_equilibrium
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
- maxcut_op89_exists_of_card_le_two_mul_add_oneFor every integer k ≥ 3 and every finite simple graph G on at most 2k+1 vertices, the unweighted Max-k-Cut game on (G,k) admits an optimal…
- maxcut_pinned_twins_refutes_of_rigidityIf every optimum of the explicit pinned-twin graph is its displayed initial coloring up to a global color permutation, then this graph has…
- maxcut_op89_exists_of_colorableIf a finite simple graph admits a proper k-colouring, then the unweighted Max-k-Cut game on (G,k) has an optimal colouring that is a…
- maxcut_op89_optimal_strong_equilibrium_negationIt is not true that for every finite type V, simple graph G on V with decidable adjacency, and k ≥ 3, the unweighted Max-k-Cut game on G…
- maxcut_op89_exists_of_card_leFor every integer k ≥ 3, every finite simple graph on at most 2k vertices admits an optimal coloring that is a strong equilibrium in the…
- maxcut_op89_exists_of_max_degree_leFor every integer k ≥ 3 and every finite simple graph G whose maximum degree is at most 2k - 1, the unweighted Max-k-Cut game admits an…
- maxcut_op89_exists_of_max_degree_fiveFor every integer k ≥ 3 and every finite simple graph G whose maximum degree is at most 5, the unweighted Max-k-Cut game admits an optimal…
- maxcut_op89_residual_exists_negationThe residual case maxcut_op89_residual_exists of OP-89 is false: it is not true that every finite simple graph G with k ≥ 3, at least 2k+2…
- maxcut_strong_equilibrium_reduce_dense_coreFix k at least three. If every finite graph of minimum degree at least k, with preconnected vertex deletions and with some vertex of…
- chordal_maxcut_optimal_strong_equilibrium_of_card_leFor every finite simple chordal graph G on at most 2k + 1 vertices and every integer k ≥ 3, the unweighted Max-k-Cut game admits an…
- chordal_maxcut_optimal_strong_equilibrium_of_max_degree_leFor every finite simple chordal graph G whose maximum degree is at most 2k - 1 and every integer k ≥ 3, the unweighted Max-k-Cut game…
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 σ