AFTD Auto-Formalizing Theoretical Domains

maxcut_pinned_twins_displayed_deviation

theoremverified

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

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.

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

    lines 1–4

    private instance maxcut_pinned_twins_displayed_deviation_pinned_graph_decidable :
        DecidableRel maxcut_pinned_twins_graph.Adj := by
      unfold maxcut_pinned_twins_graph
      infer_instance
  2. 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`.

    lines 10–13

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

    lines 15–21

    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
  4. 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⟩`.

    lines 23–29

    uses maxcut_pinned_twins_displayed_deviation_welfare, maxcut_pinned_twins_displayed_deviation_strong

    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) := ⟨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.

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