maxcut_anchor_three_coloring_strong
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
- maxcut_anchor_three_graphThe 91-vertex graph G_3 of arXiv:2610.04948: a 16-vertex core A,B,C,D and three anchor classes of 25 vertices. Indices and colors are…
- 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_strong_equilibrium_of_ranked_neighborsA coloring is a strong equilibrium if, for every alternative color at each vertex, the earlier-ranked neighbors of that color number at…
- is_maxcut_strong_equilibriumA coloring σ is a strong equilibrium of the Max-k-Cut game if no coalition has a strong deviation from it.
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.
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.
unfold maxcut_anchor_three_graph infer_instance
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.
(by unfold maxcut_anchor_three_graph; infer_instance) 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.
uses
maxcut_strong_equilibrium_of_ranked_neighborsapply maxcut_strong_equilibrium_of_ranked_neighbors _ _ MaxcutAnchorThree.rankThe 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.
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.
- The verification of the ranked-neighbor condition across all 91 vertices and 3 colors is carried out entirely by the computational reflection of the `decide` tactic.
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 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