maxcut_op89_optimal_strong_equilibrium_negation
It 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 has an optimal coloring that is a strong equilibrium (the negation of maxcut_op89_optimal_strong_equilibrium_exists); the 182-vertex pinned twins graph with k = 3 is a counterexample.
Statement
theorem maxcut_op89_optimal_strong_equilibrium_negation : ¬ ∀ (V : Type) [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (k : ℕ), 3 ≤ k → maxcut_has_optimal_strong_equilibrium G k
- Related work
- arXiv:2610.04948, Section 4 (concluding remarks), Question 2 (OP-89): does every unweighted Max-k-Cut game admit an optimal coloring that is a strong equilibrium? Answered negatively for k = 3 by the pinned twins graph.
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- maxcut_pinned_twins_optimum_rigidityEvery welfare-maximizing 3-coloring ρ of the 182-vertex pinned twins graph maxcut_pinned_twins_graph is, up to one global permutation p of…
- 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_pinned_twins_graphA candidate counterexample graph on 182 vertices. Replace each vertex of the paper graph G_3 by two independent twins, replace each old…
- maxcut_has_optimal_strong_equilibriumIn 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…
Read back from the Lean
The theorem asserts the negation of the following statement: for every finite type V, every simple graph G on V with decidable adjacency, and every natural number k ≥ 3, there exists an assignment σ : V → Fin k that is both:
1. Max-cut optimal: for all assignments τ : V → Fin k, the welfare under τ (defined as ∑ v, maxcut_utility G τ v) is less than or equal to the welfare under σ.
2. A max-cut strong equilibrium: for every non-empty finite subset S of V and every assignment τ : V → Fin k that agrees with σ outside S (i.e., ∀ v ∉ S, τ v = σ v), it is not the case that every vertex v ∈ S strictly increases its utility (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.
The proof, explained
The proof proceeds by contradiction using the 182-vertex pinned twins graph at k = 3 as an explicit counterexample. Assuming every graph has an optimal strong equilibrium for k ≥ 3, specializing to this graph produces an optimal 3-coloring that is also a strong equilibrium. However, the optimum rigidity theorem shows all optimal 3-colorings on this graph are unique up to permutation, and this rigidity rules out being a strong equilibrium. This contradiction disproves the universal claim.
Adjacency in the pinned twins graph is decidable. automation
Unfolding the definition of `maxcut_pinned_twins_graph` reveals it as a simple graph constructed from the relation `MaxcutPinnedTwins.rel`. Typeclass inference automatically synthesizes the decidability of its adjacency relation from the decidability of that relation.
private instance maxcut_op89_optimal_strong_equilibrium_negation_dec : DecidableRel maxcut_pinned_twins_graph.Adj := by unfold maxcut_pinned_twins_graph infer_instance
The universal claim fails, as the 182-vertex pinned twins graph with k = 3 admits no optimal strong equilibrium.
Assume for contradiction that every graph admits an optimal strong equilibrium for all k ≥ 3 (hypothesis h). Specializing this assumption to the pinned twins graph and k = 3 (with 3 ≤ 3 supplied by le_rfl) produces an optimal strong equilibrium. However, maxcut_pinned_twins_optimum_rigidity proves that every optimal 3-coloring of this graph is rigid (unique up to color permutations), and maxcut_pinned_twins_refutes_of_rigidity proves that this rigidity prevents any such coloring from being a strong equilibrium. This contradiction completes the proof.
uses
maxcut_pinned_twins_refutes_of_rigidity,maxcut_pinned_twins_optimum_rigidity,le_rfltheorem maxcut_op89_optimal_strong_equilibrium_negation : ¬ ∀ (V : Type) [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (k : ℕ), 3 ≤ k → maxcut_has_optimal_strong_equilibrium G k := fun h => maxcut_pinned_twins_refutes_of_rigidity maxcut_pinned_twins_optimum_rigidity (h _ maxcut_pinned_twins_graph 3 le_rfl)
maxcut_pinned_twins_optimum_rigidity- Every welfare-optimal 3-coloring of the pinned twins graph is rigid, coinciding with the canonical initial coloring up to a permutation of the three colors.
maxcut_pinned_twins_refutes_of_rigidity- If all welfare-optimal 3-colorings of the pinned twins graph are rigid, then the graph does not admit any optimal strong equilibrium for k = 3.
le_rfl- Any element in a preorder is less than or equal to itself (here, 3 ≤ 3).
- Establishing decidability of adjacency (`DecidableRel`) for the counterexample graph via a private instance is a formal Lean typeclass requirement for instantiating the universal hypothesis, with no mathematical content on paper.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
private instance maxcut_op89_optimal_strong_equilibrium_negation_dec : DecidableRel maxcut_pinned_twins_graph.Adj := by unfold maxcut_pinned_twins_graph infer_instancetheorem maxcut_op89_optimal_strong_equilibrium_negation : ¬ ∀ (V : Type) [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (k : ℕ), 3 ≤ k → maxcut_has_optimal_strong_equilibrium G k := fun h => maxcut_pinned_twins_refutes_of_rigidity maxcut_pinned_twins_optimum_rigidity (h _ maxcut_pinned_twins_graph 3 le_rfl)