AFTD Auto-Formalizing Theoretical Domains

maxcut_pinned_twins_refutes_of_rigidity

theoremverified

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

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.

  1. 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.

    lines 2–3

      unfold maxcut_pinned_twins_graph
      infer_instance
  2. 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.

    line 11

      rintro ⟨σ, h_opt, h_eq⟩
  3. 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.

    line 12

      obtain ⟨p, rfl⟩ := h σ h_opt
  4. 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.

    lines 13–15

    uses maxcut_pinned_twins_displayed_deviation.2

      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)
  5. 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 τ.

    lines 16–27

    uses maxcut_utility_color_permutation

      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
  6. Contradiction with σ being a strong equilibrium.

    The strong deviation (S, τ) contradicts the assumption that σ is a strong equilibrium.

    line 28

      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

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
See it in the graphDiscuss this resultChallenge it