maxcut_fair9_normalized_certificates
For every three-color profile on the nine-vertex graph whose first vertex has color zero, if all utilities are at least four and no singleton can profitably deviate, one of the six specified target profiles is a strong deviation.
Statement
theorem maxcut_fair9_normalized_certificates : ∀ a b c d e f g h : Fin 3, let σ := maxcut_fair9_colors a b c d e f g h (∀ v : Fin 9, 4 ≤ maxcut_utility maxcut_fair9_graph σ v) → (∀ v : Fin 9, ∀ q : Fin 3, ¬ is_maxcut_strong_deviation maxcut_fair9_graph σ {v} (Function.update σ v q)) → maxcut_fair9_targets.any (fun τ => decide (maxcut_fair9_deviation σ τ)) = true
- Source
- Related work: arXiv:2610.04948, Section 4, asks whether all unweighted Max-k-Cut games have a strong equilibrium; this finite obstruction to selecting a fair Nash equilibrium was discovered in experiment 12959 and independently checked in 12961, 12964 and 12973.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- maxcut_fair9_graphThe explicit nine-vertex simple graph used to obstruct fair Nash selection.
- maxcut_fair9_colorsThe nine-vertex three-color profile whose first color is zero and whose remaining colors are specified by eight arguments.
- maxcut_fair9_targetsSix explicit three-color profiles used as finite deviation targets.
- maxcut_fair9_deviationThe target profile is a strong deviation from the source profile using exactly the vertices whose colors change.
- 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_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)…
- Used by 1
- maxcut_fair9_no_strong_with_min_fourNo strong equilibrium of the nine-vertex graph with three colors gives every vertex utility at least four.
The proof, explained
The theorem establishes that any 3-coloring of the 9-vertex graph with vertex 0 colored 0, satisfying a minimum utility of 4 at every vertex and stable against single-vertex deviations, admits a strong coalitional deviation to at least one of six target profiles. The proof is entirely computational: after establishing decidability instances for graph adjacency and coalitional deviations, it fixes the colors of vertices 1 and 2 to partition the 3^8 = 6561 normalized color profiles into nine subcases of 3^6 = 729 profiles each. Lean's kernel decision procedure (`decide +kernel`) then exhaustively checks every configuration in each subcase, confirming that no fair, locally stable profile can escape all six deviation targets.
Adjacency in `maxcut_fair9_graph` is decidable.
We unfold the definitions of `maxcut_fair9_graph` and `SimpleGraph.fromRel`. Adjacency reduces to checking whether an ordered pair of vertices belongs to the explicit list of 25 edges (or its symmetric counterpart), which Lean's typeclass inference synthesizes as decidable.
unfold maxcut_fair9_graph SimpleGraph.fromRel infer_instance
Strong coalitional deviation for an arbitrary coalition S is decidable.
We unfold `is_maxcut_strong_deviation` and `maxcut_utility`. A strong deviation requires S to be nonempty, the coloring τ to agree with σ outside S, and every vertex in S to strictly increase its utility (the number of incident cut edges). Because the graph and vertex set are finite, these conditions involve only bounded quantifiers and cardinality comparisons over finite sets, which typeclass inference synthesizes as decidable.
unfold is_maxcut_strong_deviation maxcut_utility infer_instance
Strong deviation with coalition chosen as the support of color changes is decidable.
We unfold `maxcut_fair9_deviation`, which specializes strong deviation to the coalition of vertices where τ differs from σ. Unfolding this together with the underlying definitions allows Lean's typeclass inference to synthesize decidability for the deviation predicate.
unfold maxcut_fair9_deviation is_maxcut_strong_deviation maxcut_utility infer_instance
Every fair and singleton-stable 3-coloring with vertex 0 colored 0 admits a strong deviation to one of the six target profiles. automation
We introduce the colors a, b ∈ Fin 3 of vertices 1 and 2, and exhaustively branch on all 9 pairs (a, b) ∈ (Fin 3)^2 using `fin_cases`. Each of the 9 subgoals universally quantifies over the remaining six vertex colors (c, d, e, f, g, h ∈ Fin 3), leaving a finite space of 3^6 = 729 configurations. For each subgoal, Lean's kernel decision procedure (`decide +kernel`) exhaustively evaluates the condition, confirming that whenever every vertex has utility at least 4 and no singleton coalition can profitably deviate, at least one of the six target profiles in `maxcut_fair9_targets` is a strong deviation.
intro a b fin_cases a <;> fin_cases b <;> decide +kernel
- The proof relies on computational reflection via Lean's kernel evaluator (`decide +kernel`) rather than an analytic paper proof. The search space of 3^8 = 6561 normalized color profiles is split into 9 subgoals of 3^6 = 729 profiles each (by fixing the colors of vertices 1 and 2) to keep evaluation within Lean's recursion and memory limits.
- The auxiliary private instances at lines 4–14 establish that graph adjacency and strong coalitional deviations are decidable (`DecidableRel` and `Decidable`). These are formal prerequisites allowing Lean's `decide` tactic to evaluate these finite predicates computationally.
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.
set_option maxRecDepth 200000set_option maxHeartbeats 0set_option synthInstance.maxSize 200000private instance : DecidableRel maxcut_fair9_graph.Adj := by unfold maxcut_fair9_graph SimpleGraph.fromRel infer_instanceprivate instance (σ τ : Fin 9 → Fin 3) (S : Finset (Fin 9)) : Decidable (is_maxcut_strong_deviation maxcut_fair9_graph σ S τ) := by unfold is_maxcut_strong_deviation maxcut_utility infer_instanceprivate instance (σ τ : Fin 9 → Fin 3) : Decidable (maxcut_fair9_deviation σ τ) := by unfold maxcut_fair9_deviation is_maxcut_strong_deviation maxcut_utility infer_instancetheorem maxcut_fair9_normalized_certificates : ∀ a b c d e f g h : Fin 3, let σ := maxcut_fair9_colors a b c d e f g h (∀ v : Fin 9, 4 ≤ maxcut_utility maxcut_fair9_graph σ v) → (∀ v : Fin 9, ∀ q : Fin 3, ¬ is_maxcut_strong_deviation maxcut_fair9_graph σ {v} (Function.update σ v q)) → maxcut_fair9_targets.any (fun τ => decide (maxcut_fair9_deviation σ τ)) = true := by intro a b fin_cases a <;> fin_cases b <;> decide +kernel