maxcut_defect_two_nash_equal_cut_escape
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.
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.
uses
SimpleGraph.fromReldsimp [maxcut_defect_two_escape_graph, SimpleGraph.fromRel] infer_instance
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.
dsimp [is_maxcut_strong_deviation] infer_instance
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.
uses
Subsingleton.elim,maxcut_defect_two_nash_equal_cut_escape_adjrename_i inst have : inst = maxcut_defect_two_nash_equal_cut_escape_adj := Subsingleton.elim _ _ subst this
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.
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.
- The theorem assumes an abstract decidability instance for graph adjacency; replacing this with the concrete computable instance via Subsingleton.elim is a Lean formalization detail with no counterpart on paper.
- All five mathematical claims (the defect bound of the initial coloring, the Nash equilibrium condition, the strong coalitional deviation, the equality of cut welfare, and the defect lower bound of the new coloring) are verified by the decide tactic through finite exhaustive computation rather than symbolic deductions.
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.
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