AFTD Auto-Formalizing Theoretical Domains

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