maxcut_optimal_not_strong_degree_66
There is a finite simple graph of maximum degree at most 66 with an optimal coloring of the Max-3-Cut game that is not a strong equilibrium; hence Δ*(3) ≤ 65. (The graph G_3 of arXiv:2610.04948, Sec. 2, has 91 vertices and maximum degree 66, attained by the anchor vertices r_{3,1}.)
Statement
theorem maxcut_optimal_not_strong_degree_66 : ¬ maxcut_optimal_strong_up_to_degree 3 66- Formalizes
- arXiv:2610.04948, Theorem 2 for k = 3, with the degree bound read off the construction G_3 of Sec. 2.1 (the paper does not state the degree); the upper-bound side of list entry OP-86, a question proposed here from Corollary 9 (the known bound Δ ≤ 2k − 1 of Carosi et al., which the paper recovers).
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- maxcut_optimal_strong_up_to_degreeFor k and D: on every finite simple graph of maximum degree at most D, every optimal coloring of the Max-k-Cut game with k colors is a…
- 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…
- 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_anchor_three_stable_coloringThe paper’s displayed post-deviation coloring on G_3: A has color 2, B color 0, C and D color 1, and anchor class j has color j, using…
- maxcut_anchor_three_initial_optimalThe displayed initial coloring sigma of the 91-vertex graph G_3 in arXiv:2610.04948 maximizes social welfare among all three-colorings.
- 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…
- is_maxcut_strong_equilibriumA coloring σ is a strong equilibrium of the Max-k-Cut game if no coalition has a strong deviation from it.
- VThe ambient space $V = \mathbb{F}_p^n \times \mathbb{F}_p^n$ of pairs of coordinate vectors.
The proof, explained
The theorem is proved by contradiction using an explicit counterexample graph G on 91 vertices (16 core vertices and 75 anchor vertices) equipped with an optimal 3-coloring. First, the maximum degree of G is bounded by 66: each core vertex has degree at most 66 by finite evaluation, and each anchor vertex connects to exactly 50 other anchor vertices and at most 16 core vertices. Second, an alternative coloring is shown by finite evaluation to be a beneficial coalition deviation for the 16 core vertices, where each strictly increases its utility while anchor colors stay unchanged. Consequently, this optimal coloring is not a strong equilibrium, showing that maximum degree 66 does not guarantee strong equilibrium for optimal colorings.
Adjacency in the graph G is decidable.
Unfolding the definitions of G and maxcut_anchor_three_graph reveals that adjacency is defined via the underlying relation, which Lean's typeclass synthesis infers to be decidable.
private instance graph_decidable : DecidableRel G.Adj := by unfold G maxcut_anchor_three_graph infer_instance
Two anchor vertices are adjacent in G if and only if their partition indices differ.
By definition, two anchor vertices (j, i) and (l, t) are adjacent when they are distinct and j ≠ l ∨ l ≠ j. The forward direction follows immediately since either disjunct implies j ≠ l. Conversely, if j ≠ l, the vertices must be distinct (as equality would force j = l by projecting to the first coordinate via Prod.fst and Sum.inr.inj), establishing adjacency.
uses
Or.inl,congrArg,Prod.fst,Sum.inr.injprivate lemma anchor_adj (j l : Fin 3) (i t : Fin 25) : G.Adj (.inr (j,i)) (.inr (l,t)) ↔ j ≠ l := by change ((Sum.inr (j,i) : V) ≠ Sum.inr (l,t) ∧ (j ≠ l ∨ l ≠ j)) ↔ j ≠ l constructor · rintro ⟨_, h | h⟩ · exact h · exact h.symm · intro h refine ⟨?_, Or.inl h⟩ intro heq exact h (congrArg Prod.fst (Sum.inr.inj heq))
Every core vertex has degree at most 66 in G, establishing the degree bound in the core case.
The degree bound deg(u) ≤ 66 is verified for each of the 16 core vertices by exhaustive evaluation (`decide`). For an arbitrary vertex v, splitting on whether v is a core vertex (Sum.inl u) or an anchor vertex (Sum.inr a) immediately dispatches the core vertex case.
private lemma degree_bound : ∀ v, G.degree v ≤ 66 := by have hcore : ∀ u : Fin 16, G.degree (Sum.inl u) ≤ 66 := by decide intro v cases v with | inl u => exact hcore u
An anchor vertex has exactly 50 neighbors among the anchor vertices.
The degree of an anchor vertex (j, i) is rewritten as the sum of indicator functions over the vertex type, split via Fintype.sum_sum_type into sums over core and anchor vertices. Applying Fintype.sum_prod_type and rewriting adjacency via anchor_adj reduces the anchor-anchor neighbor count to an iterated sum over x ∈ Fin 3 and y ∈ Fin 25 of (if j ≠ x then 1 else 0). Case analysis on j ∈ {0, 1, 2} evaluates this sum to 50 in every case.
uses
SimpleGraph.card_neighborFinset_eq_degree,SimpleGraph.neighborFinset_eq_filter,Finset.card_filter,Fintype.sum_sum_type,Fintype.sum_prod_type,anchor_adj| inr a => rcases a with ⟨j,i⟩ rw [← SimpleGraph.card_neighborFinset_eq_degree, SimpleGraph.neighborFinset_eq_filter, Finset.card_filter, Fintype.sum_sum_type] have ha : (∑ w : Fin 3 × Fin 25, if G.Adj (.inr (j,i)) (.inr w) then 1 else 0) = 50 := by rw [Fintype.sum_prod_type] simp_rw [anchor_adj] fin_cases j <;> decideAn anchor vertex has at most 16 neighbors among the core vertices.
The number of core neighbors of an anchor vertex is a sum over the 16 core vertices of an indicator taking value 0 or 1. Bounding each term by 1 via Finset.sum_le_sum shows that this sum is at most 16.
uses
Finset.sum_le_sumhave hb : (∑ u : Fin 16, if G.Adj (.inr (j,i)) (.inl u) then 1 else 0) ≤ 16 := by calc _ ≤ ∑ _u : Fin 16, 1 := Finset.sum_le_sum (fun u _ => by split_ifs <;> omega) _ = 16 := by decide
Every anchor vertex has degree at most 66 in G, completing the proof that G has maximum degree at most 66.
Substituting the exact value of 50 anchor neighbors into the total degree formula, linear arithmetic (`omega`) combines this with the bound of at most 16 core neighbors to conclude that the total degree is at most 16 + 50 = 66.
rw [ha] omega
The set of 16 core vertices forms a strict beneficial coalition deviation from the initial coloring to the stable coloring. automation
A strong deviation requires that the deviating coalition is nonempty, all non-deviating vertices retain their colors, and every deviating vertex strictly increases its utility. Unfolding is_maxcut_strong_deviation, finite exhaustive evaluation (`decide`) confirms that all three conditions hold for the 16 core vertices.
private lemma deviation : is_maxcut_strong_deviation G maxcut_anchor_three_initial_coloring (Finset.univ.filter fun v : V => v.isLeft) maxcut_anchor_three_stable_coloring := by unfold is_maxcut_strong_deviation decide
Not every optimal 3-coloring in a graph of maximum degree at most 66 is a strong equilibrium.
Assume for contradiction that every optimal 3-coloring in a graph of maximum degree at most 66 is a strong equilibrium. Applying this hypothesis to G, the degree bound of 66, the initial coloring, and its optimality (maxcut_anchor_three_initial_optimal) implies that the initial coloring must be a strong equilibrium. But MaxcutDegree66Check.deviation exhibits an explicit strong coalition deviation by the 16 core vertices, yielding a contradiction.
uses
MaxcutDegree66Check.degree_bound,maxcut_anchor_three_initial_optimal,MaxcutDegree66Check.deviationtheorem maxcut_optimal_not_strong_degree_66 : ¬ maxcut_optimal_strong_up_to_degree 3 66 := by intro h have hs := h (Fin 16 ⊕ (Fin 3 × Fin 25)) maxcut_anchor_three_graph MaxcutDegree66Check.degree_bound maxcut_anchor_three_initial_coloring maxcut_anchor_three_initial_optimal exact hs _ _ MaxcutDegree66Check.deviation
Or.inl- Given a proof of P, produces a proof of the disjunction P ∨ Q.
congrArg- Equality is preserved under function application: if x = y, then f(x) = f(y).
Prod.fst- The first projection function mapping a pair (x, y) to x.
Sum.inr.inj- The right injection of a disjoint sum is injective: Sum.inr x = Sum.inr y implies x = y.
SimpleGraph.card_neighborFinset_eq_degree- The degree of a vertex in a simple graph equals the number of elements in its neighbor finset.
SimpleGraph.neighborFinset_eq_filter- The neighbor finset of a vertex v consists of all vertices w adjacent to v.
Finset.card_filter- The number of elements in a finite set satisfying a predicate equals the sum of the indicator function of that predicate over the set.
Fintype.sum_sum_type- A sum over a disjoint sum type α ⊕ β splits into the sum over α plus the sum over β.
Fintype.sum_prod_type- A sum over a product type α × β can be written as an iterated sum over α and then β.
anchor_adj- Two anchor vertices (j, i) and (l, t) are adjacent in G if and only if their color indices differ (j ≠ l).
Finset.sum_le_sum- If f(x) ≤ g(x) for all x in a finite set, then the sum of f over that set is at most the sum of g.
MaxcutDegree66Check.degree_bound- Every vertex in the graph G has degree at most 66.
maxcut_anchor_three_initial_optimal- The initial 3-coloring of G achieves maximum welfare (total cut value) among all 3-colorings.
MaxcutDegree66Check.deviation- The coalition of 16 core vertices forms a valid strong deviation from the initial coloring to the stable coloring.
- The fact that the initial coloring is optimal (maxcut_anchor_three_initial_optimal) is proven as a separate theorem in the knowledge base and imported here.
- The degree bound for core vertices and the coalitional deviation condition (verifying that all 16 core vertices strictly improve their utility) are discharged by exhaustive finite computation (`decide`).
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.
open scoped BigOperatorsnamespace MaxcutDegree66Checkprivate abbrev V := Fin 16 ⊕ (Fin 3 × Fin 25)private abbrev G := maxcut_anchor_three_graphprivate instance graph_decidable : DecidableRel G.Adj := by unfold G maxcut_anchor_three_graph infer_instanceset_option maxRecDepth 200000set_option maxHeartbeats 0set_option synthInstance.maxSize 200000private lemma anchor_adj (j l : Fin 3) (i t : Fin 25) : G.Adj (.inr (j,i)) (.inr (l,t)) ↔ j ≠ l := by change ((Sum.inr (j,i) : V) ≠ Sum.inr (l,t) ∧ (j ≠ l ∨ l ≠ j)) ↔ j ≠ l constructor · rintro ⟨_, h | h⟩ · exact h · exact h.symm · intro h refine ⟨?_, Or.inl h⟩ intro heq exact h (congrArg Prod.fst (Sum.inr.inj heq))private lemma degree_bound : ∀ v, G.degree v ≤ 66 := by have hcore : ∀ u : Fin 16, G.degree (Sum.inl u) ≤ 66 := by decide intro v cases v with | inl u => exact hcore u | inr a => rcases a with ⟨j,i⟩ rw [← SimpleGraph.card_neighborFinset_eq_degree, SimpleGraph.neighborFinset_eq_filter, Finset.card_filter, Fintype.sum_sum_type] have ha : (∑ w : Fin 3 × Fin 25, if G.Adj (.inr (j,i)) (.inr w) then 1 else 0) = 50 := by rw [Fintype.sum_prod_type] simp_rw [anchor_adj] fin_cases j <;> decide have hb : (∑ u : Fin 16, if G.Adj (.inr (j,i)) (.inl u) then 1 else 0) ≤ 16 := by calc _ ≤ ∑ _u : Fin 16, 1 := Finset.sum_le_sum (fun u _ => by split_ifs <;> omega) _ = 16 := by decide rw [ha] omegaprivate lemma deviation : is_maxcut_strong_deviation G maxcut_anchor_three_initial_coloring (Finset.univ.filter fun v : V => v.isLeft) maxcut_anchor_three_stable_coloring := by unfold is_maxcut_strong_deviation decideend MaxcutDegree66Checktheorem maxcut_optimal_not_strong_degree_66 : ¬ maxcut_optimal_strong_up_to_degree 3 66 := by intro h have hs := h (Fin 16 ⊕ (Fin 3 × Fin 25)) maxcut_anchor_three_graph MaxcutDegree66Check.degree_bound maxcut_anchor_three_initial_coloring maxcut_anchor_three_initial_optimal exact hs _ _ MaxcutDegree66Check.deviation