maxcut_pinned_twins_displayed_deviation
The pinned-twin graph has an initial coloring of welfare 16376 and a strong deviation consisting of all 32 core twins to the doubled post-deviation coloring. This does not assert optimality or exclude other optimal colorings.
Statement
theorem maxcut_pinned_twins_displayed_deviation : maxcut_welfare maxcut_pinned_twins_graph (fun v => maxcut_anchor_three_initial_coloring v.1) = 16376 ∧ is_maxcut_strong_deviation maxcut_pinned_twins_graph (fun v => maxcut_anchor_three_initial_coloring v.1) (Finset.univ.filter fun v => v.1.isLeft) (fun v => maxcut_anchor_three_stable_coloring v.1)
- Source
- Concrete witness check for the new OP-89 pinned-twin construction. The computational quotient check is experiment 5022. Every core twin gains one utility unit; Lean checks the strong deviation and initial welfare directly on all 182 vertices.
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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_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.
- 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…
- Used by 1
- 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…
The proof, explained
The theorem establishes two properties of the max-cut game on the pinned-twin graph: that an initial 3-coloring has total welfare 16376, and that a collective switch of the 32 core twin vertices to an alternative coloring is a strong deviation (strictly improving the cut utility of every deviating vertex while leaving all other vertices unchanged). Both lemmas are verified by exhaustive computation on the finite graph using `decide`, and the theorem bundles them together into a conjunction.
Adjacency in the pinned-twin graph is computationally decidable.
Unfolding the definition of `maxcut_pinned_twins_graph` expresses it as a graph built from a relation on a finite product type, allowing typeclass synthesis (`infer_instance`) to establish that edge adjacency is decidable.
private instance maxcut_pinned_twins_displayed_deviation_pinned_graph_decidable : DecidableRel maxcut_pinned_twins_graph.Adj := by unfold maxcut_pinned_twins_graph infer_instance
The total welfare of the initial 3-coloring is 16376. automation
The welfare is the sum over all 182 vertices of the number of incident cut edges. Because the graph and colorings are completely explicit and finite, the equality is verified by exhaustive computation using `decide`.
private lemma maxcut_pinned_twins_displayed_deviation_welfare : maxcut_welfare maxcut_pinned_twins_graph (fun v => maxcut_anchor_three_initial_coloring v.1) = 16376 := by decide
The deviation of all 32 core twin vertices to the stable coloring is a strong deviation. automation
Unfolding the definition of `is_maxcut_strong_deviation` requires showing three conditions: the deviating coalition of core twins is nonempty, non-coalition vertices retain their original colors, and each of the 32 core twin vertices strictly increases its cut utility. Since all parameters are finite and decidable, `decide` verifies all conditions by finite evaluation.
private lemma maxcut_pinned_twins_displayed_deviation_strong : is_maxcut_strong_deviation maxcut_pinned_twins_graph (fun v => maxcut_anchor_three_initial_coloring v.1) (Finset.univ.filter fun v => v.1.isLeft) (fun v => maxcut_anchor_three_stable_coloring v.1) := by unfold is_maxcut_strong_deviation decide
The pinned-twin graph satisfies both the welfare evaluation and the strong deviation property.
The main theorem packages the two established facts into a conjunction using `⟨maxcut_pinned_twins_displayed_deviation_welfare, maxcut_pinned_twins_displayed_deviation_strong⟩`.
uses
maxcut_pinned_twins_displayed_deviation_welfare,maxcut_pinned_twins_displayed_deviation_strongtheorem maxcut_pinned_twins_displayed_deviation : maxcut_welfare maxcut_pinned_twins_graph (fun v => maxcut_anchor_three_initial_coloring v.1) = 16376 ∧ is_maxcut_strong_deviation maxcut_pinned_twins_graph (fun v => maxcut_anchor_three_initial_coloring v.1) (Finset.univ.filter fun v => v.1.isLeft) (fun v => maxcut_anchor_three_stable_coloring v.1) := ⟨maxcut_pinned_twins_displayed_deviation_welfare, maxcut_pinned_twins_displayed_deviation_strong⟩
maxcut_pinned_twins_displayed_deviation_welfare- The initial 3-coloring on the pinned-twin graph achieves a total welfare (sum of cut degrees across all vertices) of 16376.
maxcut_pinned_twins_displayed_deviation_strong- The collective deviation of the 32 core vertices from the initial coloring to the stable coloring forms a strong deviation, strictly increasing each deviating vertex's cut utility while leaving other vertices unaffected.
- Both the welfare evaluation and the verification of the strong deviation are carried out entirely by Lean's computational reflection/evaluation tactic (`decide`) over the explicit 182-vertex graph, with memory and recursion limits raised to accommodate the large finite computation.
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_displayed_deviation_pinned_graph_decidable : DecidableRel maxcut_pinned_twins_graph.Adj := by unfold maxcut_pinned_twins_graph infer_instanceset_option maxRecDepth 200000set_option maxHeartbeats 0set_option synthInstance.maxSize 200000private lemma maxcut_pinned_twins_displayed_deviation_welfare : maxcut_welfare maxcut_pinned_twins_graph (fun v => maxcut_anchor_three_initial_coloring v.1) = 16376 := by decideprivate lemma maxcut_pinned_twins_displayed_deviation_strong : is_maxcut_strong_deviation maxcut_pinned_twins_graph (fun v => maxcut_anchor_three_initial_coloring v.1) (Finset.univ.filter fun v => v.1.isLeft) (fun v => maxcut_anchor_three_stable_coloring v.1) := by unfold is_maxcut_strong_deviation decidetheorem maxcut_pinned_twins_displayed_deviation : maxcut_welfare maxcut_pinned_twins_graph (fun v => maxcut_anchor_three_initial_coloring v.1) = 16376 ∧ is_maxcut_strong_deviation maxcut_pinned_twins_graph (fun v => maxcut_anchor_three_initial_coloring v.1) (Finset.univ.filter fun v => v.1.isLeft) (fun v => maxcut_anchor_three_stable_coloring v.1) := ⟨maxcut_pinned_twins_displayed_deviation_welfare, maxcut_pinned_twins_displayed_deviation_strong⟩