maxcut_anchor_neutral_pivot_initial_strong
theoremverified
The displayed initial profile is a strong equilibrium after the extra edge is added.
Statement
theorem maxcut_anchor_neutral_pivot_initial_strong : is_maxcut_strong_equilibrium maxcut_anchor_neutral_pivot_graph maxcut_anchor_three_initial_coloring- Source
- Independent SAT and CP-SAT checks 16812 and 16814.
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- maxcut_anchor_neutral_pivot_graphThe known 91-vertex anchor graph with one extra edge from the first core vertex to a previously nonadjacent anchor of its displayed target…
- 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_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)…
- maxcut_cycle71_first_deviation_minimalThe 32 core vertices have a profitable deviation from the first displayed profile to the second, and no proper subcoalition can profitably…
- 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_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…
- 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…
Lean source view module on GitHub
instance : DecidableRel maxcut_anchor_neutral_pivot_graph.Adj := by unfold maxcut_anchor_neutral_pivot_graph maxcut_anchor_three_graph infer_instance set_option maxHeartbeats 1000000 private def maxcut_anchor_neutral_pivot_initial_rank : (Fin 16 ⊕ (Fin 3 × Fin 25)) → ℕ | Sum.inl u => match u.val with | 0 => 2 | 5 | 6 | 7 => 3 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 => 4 | _ => 5 | Sum.inr (j, i) => if (j.val = 1 ∧ i.val = 0) ∨ (j.val = 2 ∧ i.val = 0) then 1 else 0 theorem maxcut_anchor_neutral_pivot_initial_strong : is_maxcut_strong_equilibrium maxcut_anchor_neutral_pivot_graph maxcut_anchor_three_initial_coloring := by apply maxcut_strong_equilibrium_of_ranked_neighbors _ _ maxcut_anchor_neutral_pivot_initial_rank decide