maxcut_pinned_twins_refutes_of_rigidity
If every optimum of the explicit pinned-twin graph is its displayed initial coloring up to a global color permutation, then this graph has no optimal strong equilibrium.
Statement
theorem maxcut_pinned_twins_refutes_of_rigidity (h : ∀ ρ : ((Fin 16 ⊕ (Fin 3 × Fin 25)) × Fin 2) → Fin 3, is_maxcut_optimal maxcut_pinned_twins_graph ρ → ∃ p : Equiv.Perm (Fin 3), ρ = fun v => p (maxcut_anchor_three_initial_coloring v.1)) : ¬ maxcut_has_optimal_strong_equilibrium maxcut_pinned_twins_graph 3
- Source
- Conditional refutation criterion for OP-89. The displayed deviation is Lean checked; all-optimum rigidity of this graph remains unproved. This conditional theorem does not settle OP-89.
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 11
- 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_anchor_three_initial_coloringThe initial coloring sigma of the paper graph G_3: A and D have color 0, B color 1, C color 2, and anchor class j has color j.
- maxcut_anchor_three_stable_coloringThe paper’s displayed post-deviation coloring on G_3: A has color 2, B color 0, C and D color 1, and anchor class j has color j, using…
- maxcut_pinned_twins_displayed_deviationThe pinned-twin graph has an initial coloring of welfare 16376 and a strong deviation consisting of all 32 core twins to the doubled…
- maxcut_utility_color_permutationPermuting all color labels preserves every player’s utility in the Max-k-Cut game.
- is_maxcut_optimalA coloring σ is optimal if no coloring τ : V → [k] has larger social welfare (equivalently, σ is a maximum k-cut).
- 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…
- 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)…
- is_maxcut_strong_deviationA strong deviation from σ is a nonempty coalition S ⊆ V with a coloring τ agreeing with σ outside S such that u_v(τ) > u_v(σ) for every v…
- is_maxcut_strong_equilibriumA coloring σ is a strong equilibrium of the Max-k-Cut game if no coalition has a strong deviation from it.
- maxcut_welfareThe social welfare of a coloring σ in the Max-k-Cut game: the sum over all players v of u_v(σ), equal to twice the cut value.
- Used by 2
- 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_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…
The proof, explained
Assuming there is an optimal strong equilibrium, the rigidity hypothesis implies it must be the initial coloring up to a global permutation of the three colors. However, the known strong deviation on the left-summand vertices transfers directly under color permutations, because local utilities are invariant under permuting the color labels. This produces a profitable coalition deviation, contradicting the equilibrium assumption.
Adjacency in the pinned-twin graph is decidable.
Unfolding the definition of the pinned-twin graph shows that its adjacency relation is decidable by typeclass resolution.
unfold maxcut_pinned_twins_graph infer_instance
Assume for contradiction that there exists an optimal strong equilibrium σ.
Suppose there exists a 3-coloring σ that is both Max-Cut optimal and a strong equilibrium.
rintro ⟨σ, h_opt, h_eq⟩
The coloring σ is a color permutation of the initial coloring.
By the rigidity hypothesis, since σ is optimal, there is a permutation p of the three colors such that σ is the initial coloring composed with p.
obtain ⟨p, rfl⟩ := h σ h_opt
Extract the deviation properties for the unpermuted coloring and define the coalition S and deviated coloring τ.
From maxcut_pinned_twins_displayed_deviation, the coalition S of vertices in the left summand is nonempty, vertices outside S have identical colors in both colorings, and vertices in S strictly gain utility under the stable coloring. We define τ by applying the same permutation p to the stable coloring.
uses
maxcut_pinned_twins_displayed_deviation.2obtain ⟨h_ne, h_out, h_in⟩ := maxcut_pinned_twins_displayed_deviation.2 set S : Finset (((Fin 16 ⊕ (Fin 3 × Fin 25)) × Fin 2)) := Finset.univ.filter (fun v => v.1.isLeft) set τ := fun v : ((Fin 16 ⊕ (Fin 3 × Fin 25)) × Fin 2) => p (maxcut_anchor_three_stable_coloring v.1)
The permuted stable coloring τ is a strong deviation from σ for coalition S.
S is nonempty. Outside S, τ and σ agree because the unpermuted colorings agree. For any vertex in S, applying maxcut_utility_color_permutation shows that the utilities under σ and τ match the unpermuted utilities, so utility strictly increases from σ to τ.
uses
maxcut_utility_color_permutationhave h_dev_p : is_maxcut_strong_deviation maxcut_pinned_twins_graph (fun v => p (maxcut_anchor_three_initial_coloring v.1)) S τ := by refine ⟨h_ne, ?_, ?_⟩ · intro v hv dsimp [τ] have hv_eq := h_out v hv dsimp at hv_eq rw [hv_eq] · intro v hv rw [maxcut_utility_color_permutation maxcut_pinned_twins_graph (fun w => maxcut_anchor_three_initial_coloring w.1) p v] rw [maxcut_utility_color_permutation maxcut_pinned_twins_graph (fun w => maxcut_anchor_three_stable_coloring w.1) p v] exact h_in v hv
Contradiction with σ being a strong equilibrium.
The strong deviation (S, τ) contradicts the assumption that σ is a strong equilibrium.
exact h_eq S τ h_dev_p
maxcut_pinned_twins_refutes_of_rigidity_pinned_graph_decidable- Adjacency in the pinned-twin graph is decidable.
maxcut_pinned_twins_displayed_deviation.2- The displayed stable coloring is a strong deviation from the initial coloring for the coalition of left-summand vertices.
maxcut_utility_color_permutation- Permuting the colors globally does not change any vertex's Max-Cut utility.
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_pinned_twins_refutes_of_rigidity_pinned_graph_decidable : DecidableRel maxcut_pinned_twins_graph.Adj := by unfold maxcut_pinned_twins_graph infer_instancetheorem maxcut_pinned_twins_refutes_of_rigidity (h : ∀ ρ : ((Fin 16 ⊕ (Fin 3 × Fin 25)) × Fin 2) → Fin 3, is_maxcut_optimal maxcut_pinned_twins_graph ρ → ∃ p : Equiv.Perm (Fin 3), ρ = fun v => p (maxcut_anchor_three_initial_coloring v.1)) : ¬ maxcut_has_optimal_strong_equilibrium maxcut_pinned_twins_graph 3 := by rintro ⟨σ, h_opt, h_eq⟩ obtain ⟨p, rfl⟩ := h σ h_opt obtain ⟨h_ne, h_out, h_in⟩ := maxcut_pinned_twins_displayed_deviation.2 set S : Finset (((Fin 16 ⊕ (Fin 3 × Fin 25)) × Fin 2)) := Finset.univ.filter (fun v => v.1.isLeft) set τ := fun v : ((Fin 16 ⊕ (Fin 3 × Fin 25)) × Fin 2) => p (maxcut_anchor_three_stable_coloring v.1) have h_dev_p : is_maxcut_strong_deviation maxcut_pinned_twins_graph (fun v => p (maxcut_anchor_three_initial_coloring v.1)) S τ := by refine ⟨h_ne, ?_, ?_⟩ · intro v hv dsimp [τ] have hv_eq := h_out v hv dsimp at hv_eq rw [hv_eq] · intro v hv rw [maxcut_utility_color_permutation maxcut_pinned_twins_graph (fun w => maxcut_anchor_three_initial_coloring w.1) p v] rw [maxcut_utility_color_permutation maxcut_pinned_twins_graph (fun w => maxcut_anchor_three_stable_coloring w.1) p v] exact h_in v hv exact h_eq S τ h_dev_p