AFTD Auto-Formalizing Theoretical Domains

maxcut_anchor_three_coloring_strong

theoremverifiedoriginal

The displayed post-deviation coloring tau is a strong equilibrium on the paper’s explicit graph G_3. This theorem proves stability only; optimality of the construction is not formalized here.

Statement

theorem maxcut_anchor_three_coloring_strong :
    @is_maxcut_strong_equilibrium _ _ maxcut_anchor_three_graph
      (by unfold maxcut_anchor_three_graph; infer_instance) 3
      maxcut_anchor_three_stable_coloring
Related work
OP-89, arXiv:2610.04948 Secs. 2 and 4. The paper supplies G_3 and tau; this check adds a strong-equilibrium certificate for tau. It is a diagnostic example for the stable-optimum question and is not marked as a research advance.
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4

The proof, explained

To prove that maxcut_anchor_three_stable_coloring is a strong equilibrium of the 3-cut game on maxcut_anchor_three_graph, the proof applies the reduction lemma maxcut_strong_equilibrium_of_ranked_neighbors using an explicit vertex ranking function MaxcutAnchorThree.rank. This reduces the statement to checking that for every vertex and every alternative color, the number of same-color neighbors is at most the number of lower-ranked neighbors of the alternative color. Because the graph and color set are finite, Lean's decide tactic verifies this local condition by exhaustive computation.

  1. Adjacency in maxcut_anchor_three_graph is decidable.

    By unfolding maxcut_anchor_three_graph into SimpleGraph.fromRel MaxcutAnchorThree.rel, typeclass synthesis (infer_instance) establishes that graph adjacency is decidable.

    lines 2–3

      unfold maxcut_anchor_three_graph
      infer_instance
  2. Adjacency in maxcut_anchor_three_graph is decidable, supplying the typeclass argument required by is_maxcut_strong_equilibrium.

    In the theorem statement, the explicit DecidableRel argument to is_maxcut_strong_equilibrium is supplied inline by unfolding the graph definition and calling infer_instance.

    line 17

          (by unfold maxcut_anchor_three_graph; infer_instance) 3
  3. To show that the coloring is a strong equilibrium, it suffices to show that for every vertex v and each alternative color c ≠ σ(v), the number of neighbors sharing v's color is at most the number of lower-ranked neighbors with color c under MaxcutAnchorThree.rank.

    We apply maxcut_strong_equilibrium_of_ranked_neighbors with the explicit ranking function MaxcutAnchorThree.rank. This reduction lemma guarantees that such a ranked-neighbor condition prevents any coalition of vertices from strictly increasing their cut edges simultaneously.

    line 19

    uses maxcut_strong_equilibrium_of_ranked_neighbors

      apply maxcut_strong_equilibrium_of_ranked_neighbors _ _ MaxcutAnchorThree.rank
  4. The ranked-neighbor condition holds for all vertices and all alternative colors. automation

    The graph has finitely many vertices (16 + 3 × 25 = 91 vertices) and 3 colors, so the condition is a finite, decidable check over all vertices and colors. The decide tactic evaluates this inequality exhaustively across all instances.

    line 20

      decide
maxcut_strong_equilibrium_of_ranked_neighbors
A coloring of a graph is a strong equilibrium in the Max-Cut game if there exists a vertex ranking such that for every vertex v and every alternative color c, the number of neighbors sharing v's current color is at most the number of neighbors of color c having strictly lower rank than v.

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 graph_decidable : DecidableRel maxcut_anchor_three_graph.Adj := by  unfold maxcut_anchor_three_graph  infer_instancenamespace MaxcutAnchorThreeprivate def rank : (Fin 16 ⊕ (Fin 3 × Fin 25)) → ℕ  | .inl u => if 4 ≤ u.val ∧ u.val < 12 then 0 else 2  | .inr (j, i) => if (j.val = 1 ∨ j.val = 2) ∧ i.val < 3 then 1 else 0end MaxcutAnchorThreeset_option maxRecDepth 200000set_option maxHeartbeats 0set_option synthInstance.maxSize 200000theorem maxcut_anchor_three_coloring_strong :    @is_maxcut_strong_equilibrium _ _ maxcut_anchor_three_graph      (by unfold maxcut_anchor_three_graph; infer_instance) 3      maxcut_anchor_three_stable_coloring := by  apply maxcut_strong_equilibrium_of_ranked_neighbors _ _ MaxcutAnchorThree.rank  decide
See it in the graphDiscuss this resultChallenge it