AFTD Auto-Formalizing Theoretical Domains

maxcut_defect_two_nash_equal_cut_escape

theoremverified

A defect-two Nash coloring can have a strong deviation of equal welfare to a coloring of defect at least four.

Statement

theorem maxcut_defect_two_nash_equal_cut_escape
    [DecidableRel maxcut_defect_two_escape_graph.Adj] :
    (∀ v : Fin 15, (Finset.univ.filter fun w => maxcut_defect_two_escape_graph.Adj v w ∧
      (![0,0,0,0,1,1,1,1,2,2,2,2,0,1,2] : Fin 15 → Fin 3) w = (![0,0,0,0,1,1,1,1,2,2,2,2,0,1,2] : Fin 15 → Fin 3) v).card ≤ 2) ∧
    (∀ v : Fin 15, ∀ c : Fin 3, ¬ is_maxcut_strong_deviation maxcut_defect_two_escape_graph
      (![0,0,0,0,1,1,1,1,2,2,2,2,0,1,2] : Fin 15 → Fin 3) {v} (Function.update (![0,0,0,0,1,1,1,1,2,2,2,2,0,1,2] : Fin 15 → Fin 3) v c)) ∧
    is_maxcut_strong_deviation maxcut_defect_two_escape_graph (![0,0,0,0,1,1,1,1,2,2,2,2,0,1,2] : Fin 15 → Fin 3)
      (Finset.univ.filter fun v : Fin 15 => v.val < 12) (![1,2,1,2,2,0,2,0,0,1,0,1,0,1,2] : Fin 15 → Fin 3) ∧
    maxcut_welfare maxcut_defect_two_escape_graph (![0,0,0,0,1,1,1,1,2,2,2,2,0,1,2] : Fin 15 → Fin 3) = maxcut_welfare maxcut_defect_two_escape_graph (![1,2,1,2,2,0,2,0,0,1,0,1,0,1,2] : Fin 15 → Fin 3) ∧
    ∃ v : Fin 15, 4 ≤ (Finset.univ.filter fun w => maxcut_defect_two_escape_graph.Adj v w ∧
      (![1,2,1,2,2,0,2,0,0,1,0,1,0,1,2] : Fin 15 → Fin 3) w = (![1,2,1,2,2,0,2,0,0,1,0,1,0,1,2] : Fin 15 → Fin 3) v).card
Source
Independent direct verification in experiments 16323–16324.
Verified
10 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • maxcut_defect_two_escape_graphThe 15-vertex graph used for an equal-cut strong deviation from a defect-two Nash coloring.
  • 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…
  • 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.
  • 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)…

The proof, explained

The theorem is proved by finite computational verification on an explicit 15-vertex graph with 3 colors. After establishing that graph adjacency and coalitional strong deviations are decidable, the proof substitutes the concrete computable adjacency instance into the goal using subsingleton elimination. Finally, the decide tactic exhaustively checks all five conjuncts: the initial 3-coloring has defect at most 2, is a Nash equilibrium, admits a strong deviation by the first 12 vertices to a new coloring with equal total cut welfare, and the resulting coloring has defect at least 4.

  1. The adjacency relation of the 15-vertex escape graph is decidable.

    Unfolding the definitions of the graph maxcut_defect_two_escape_graph and SimpleGraph.fromRel simplifies adjacency between two vertices to the condition that they are distinct and that their pair of indices belongs to an explicit list of 48 edges. Typeclass inference (infer_instance) automatically synthesizes decidability for this finite relation.

    lines 3–4

    uses SimpleGraph.fromRel

      dsimp [maxcut_defect_two_escape_graph, SimpleGraph.fromRel]
      infer_instance
  2. Whether a coalition has a strong deviation between two colorings is decidable.

    Expanding the definition of is_maxcut_strong_deviation expresses the property as a conjunction of three conditions: the coalition S is nonempty, the new coloring agrees with the old coloring outside S, and every vertex in S strictly increases its utility (number of incident cut edges). Because the vertex set is finite (15 vertices) and utilities are cardinalities of finite filtered sets, each condition is decidable, and infer_instance synthesizes the decision procedure.

    lines 9–10

      dsimp [is_maxcut_strong_deviation]
      infer_instance
  3. The ambient decidability hypothesis for graph adjacency is replaced by the concrete computable instance.

    The theorem is stated under an assumed instance `inst` of DecidableRel maxcut_defect_two_escape_graph.Adj. Because Decidable on any proposition is a subsingleton, Subsingleton.elim shows that `inst` equals the concrete instance maxcut_defect_two_nash_equal_cut_escape_adj defined earlier. Substituting this equality replaces the abstract parameter with the executable instance, enabling evaluation.

    lines 23–25

    uses Subsingleton.elim, maxcut_defect_two_nash_equal_cut_escape_adj

      rename_i inst
      have : inst = maxcut_defect_two_nash_equal_cut_escape_adj := Subsingleton.elim _ _
      subst this
  4. The initial coloring is a defect-two Nash coloring that admits an equal-welfare strong deviation to a coloring of defect at least four. automation

    The decide tactic verifies the theorem by exhaustive finite computation over the 15-vertex graph with 3 colors: (1) every vertex has at most 2 monochromatic neighbors in the initial coloring; (2) no single vertex can strictly improve its utility by changing its color (Nash equilibrium); (3) the coalition of the first 12 vertices strictly improves every member's utility by deviating to the new coloring; (4) the total cut welfare is equal before and after the deviation; and (5) the new coloring contains a vertex with at least 4 monochromatic neighbors.

    line 26

      decide
SimpleGraph.fromRel
Constructs a simple graph from a binary relation on vertices by excluding self-loops and making edges symmetric.
Subsingleton.elim
Any two terms of a subsingleton type (a type with at most one term, such as a decidability typeclass on a proposition) are equal.
maxcut_defect_two_nash_equal_cut_escape_adj
The adjacency relation of the 15-vertex graph maxcut_defect_two_escape_graph is decidable.

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

instance maxcut_defect_two_nash_equal_cut_escape_adj :    DecidableRel maxcut_defect_two_escape_graph.Adj := by  dsimp [maxcut_defect_two_escape_graph, SimpleGraph.fromRel]  infer_instanceinstance maxcut_defect_two_nash_equal_cut_escape_dev    {k : ℕ} (σ : Fin 15 → Fin k) (S : Finset (Fin 15)) (τ : Fin 15 → Fin k) :    Decidable (is_maxcut_strong_deviation maxcut_defect_two_escape_graph σ S τ) := by  dsimp [is_maxcut_strong_deviation]  infer_instancetheorem maxcut_defect_two_nash_equal_cut_escape    [DecidableRel maxcut_defect_two_escape_graph.Adj] :    (∀ v : Fin 15, (Finset.univ.filter fun w => maxcut_defect_two_escape_graph.Adj v w ∧      (![0,0,0,0,1,1,1,1,2,2,2,2,0,1,2] : Fin 15 → Fin 3) w = (![0,0,0,0,1,1,1,1,2,2,2,2,0,1,2] : Fin 15 → Fin 3) v).card ≤ 2) ∧    (∀ v : Fin 15, ∀ c : Fin 3, ¬ is_maxcut_strong_deviation maxcut_defect_two_escape_graph      (![0,0,0,0,1,1,1,1,2,2,2,2,0,1,2] : Fin 15 → Fin 3) {v} (Function.update (![0,0,0,0,1,1,1,1,2,2,2,2,0,1,2] : Fin 15 → Fin 3) v c)) ∧    is_maxcut_strong_deviation maxcut_defect_two_escape_graph (![0,0,0,0,1,1,1,1,2,2,2,2,0,1,2] : Fin 15 → Fin 3)      (Finset.univ.filter fun v : Fin 15 => v.val < 12) (![1,2,1,2,2,0,2,0,0,1,0,1,0,1,2] : Fin 15 → Fin 3) ∧    maxcut_welfare maxcut_defect_two_escape_graph (![0,0,0,0,1,1,1,1,2,2,2,2,0,1,2] : Fin 15 → Fin 3) = maxcut_welfare maxcut_defect_two_escape_graph (![1,2,1,2,2,0,2,0,0,1,0,1,0,1,2] : Fin 15 → Fin 3) ∧    ∃ v : Fin 15, 4 ≤ (Finset.univ.filter fun w => maxcut_defect_two_escape_graph.Adj v w ∧      (![1,2,1,2,2,0,2,0,0,1,0,1,0,1,2] : Fin 15 → Fin 3) w = (![1,2,1,2,2,0,2,0,0,1,0,1,0,1,2] : Fin 15 → Fin 3) v).card := by  rename_i inst  have : inst = maxcut_defect_two_nash_equal_cut_escape_adj := Subsingleton.elim _ _  subst this  decide
See it in the graphDiscuss this resultChallenge it