maxcut_strong_equilibrium_of_ranked_neighbors
A coloring is a strong equilibrium if, for every alternative color at each vertex, the earlier-ranked neighbors of that color number at least the vertex’s current monochromatic neighbors.
Statement
theorem maxcut_strong_equilibrium_of_ranked_neighbors {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ : V → Fin k) (r : V → ℕ) (hlock : ∀ v c, c ≠ σ v → (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card ≤ (Finset.univ.filter fun w => G.Adj v w ∧ r w < r v ∧ σ w = c).card) : is_maxcut_strong_equilibrium G σ
- Source
- Certificate helper for the OP-89 investigation, arXiv:2610.04948. Earlier-ranked colors are fixed when considering the least-ranked vertex that changes color.
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- maxcut_utility_add_monochromatic_cardA player's utility plus the number of its neighbours sharing its colour equals its degree.
- maxcut_strong_deviation_carrierEvery strong deviation contains a carrier deviation: the subset of players who actually change color forms a valid strong deviation.
- is_maxcut_strong_equilibriumA coloring σ is a strong equilibrium of the Max-k-Cut game if no coalition has a strong deviation from it.
- 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 3
- maxcut_fair9_stable_exampleA specified three-color profile is a strong equilibrium of the nine-vertex graph.
- maxcut_anchor_three_coloring_strongThe displayed post-deviation coloring tau is a strong equilibrium on the paper’s explicit graph G_3. This theorem proves stability only;…
- maxcut_anchor_neutral_pivot_initial_strongThe displayed initial profile is a strong equilibrium after the extra edge is added.
The proof, explained
Suppose for contradiction that a strong deviation from σ exists. By `maxcut_strong_deviation_carrier`, the set D of vertices that actually change color is also a valid deviating coalition where every member strictly increases its cut utility. Choosing a vertex v in D of minimal rank ensures that all lower-ranked neighbors of v retain their original colors, so those initially colored τ(v) become monochromatic neighbors under τ. The ranking hypothesis then implies that v has at least as many monochromatic neighbors under τ as under σ. Since cut utility and monochromatic degree sum to the vertex degree, v cannot strictly improve its utility, yielding a contradiction.
Assuming the existence of a strong deviation, the set of vertices that change color forms a non-empty deviating coalition.
To show that σ is a strong equilibrium, we assume for contradiction that there exists a coalition S and an alternative coloring τ that strictly improves the utility of every vertex in S. By `maxcut_strong_deviation_carrier`, the set of vertices that actually change color, D = {v | τ v ≠ σ v}, is itself a valid strong deviation coalition.
uses
maxcut_strong_deviation_carrierclassical intro S τ hdev have hcarrier := maxcut_strong_deviation_carrier G σ τ S hdev
There exists a vertex v changing color whose rank r(v) is minimal among all vertices in D.
Because D is non-empty, there is an element v ∈ D that minimizes the ranking function r on D. By definition of D, the new color τ(v) is different from the original color σ(v).
let D := Finset.univ.filter fun v => τ v ≠ σ v obtain ⟨v, hv, hmin⟩ := D.exists_min_image r hcarrier.1 have hvdiff : τ v ≠ σ v := (Finset.mem_filter.mp hv).2
Every vertex with rank strictly less than r(v) retains its color under τ.
If some vertex w with r(w) < r(v) changed color, it would belong to D. By minimality of v on D, this would force r(v) ≤ r(w), contradicting r(w) < r(v).
have hfixed : ∀ w, r w < r v → τ w = σ w := by intro w hw by_contra hne have hwD : w ∈ D := Finset.mem_filter.mpr ⟨Finset.mem_univ _, hne⟩ have := hmin w hwD omega
All neighbors of v with lower rank and original color τ(v) are monochromatic neighbors of v under τ.
Let w be a neighbor of v with r(w) < r(v) and σ(w) = τ(v). Since r(w) < r(v), vertex w retains its color under τ, so τ(w) = σ(w) = τ(v). Thus w is adjacent to v and shares the color τ(v).
have hsubset : (Finset.univ.filter fun w => G.Adj v w ∧ r w < r v ∧ σ w = τ v) ⊆ (Finset.univ.filter fun w => G.Adj v w ∧ τ w = τ v) := by intro w hw obtain ⟨_, hadj, hlt, hcolor⟩ := Finset.mem_filter.mp hw exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, hadj, by rw [hfixed w hlt, hcolor]⟩
The number of monochromatic neighbors of v under τ is at least its number of monochromatic neighbors under σ.
By the ranking condition `hlock` evaluated at v and alternative color τ(v) ≠ σ(v), the number of monochromatic neighbors of v under σ is at most the number of lower-ranked neighbors with color τ(v). By `Finset.card_le_card`, this is bounded by the number of monochromatic neighbors under τ. Transitivity of inequality (`le_trans`) combines these two inequalities.
uses
le_trans,Finset.card_le_cardhave hmono := le_trans (hlock v (τ v) hvdiff) (Finset.card_le_card hsubset)The utility gain of v contradicts the increase in monochromatic neighbors. automation
By `maxcut_utility_add_monochromatic_card`, the cut utility of v plus the number of its monochromatic neighbors equals the vertex degree under both σ and τ. Since the monochromatic neighbors did not decrease, the utility cannot strictly increase. However, because v belongs to the deviation coalition D, its utility under τ must be strictly greater than under σ, yielding an arithmetic contradiction.
uses
maxcut_utility_add_monochromatic_cardhave hσ := maxcut_utility_add_monochromatic_card G σ v have hτ := maxcut_utility_add_monochromatic_card G τ v have hgain := hcarrier.2.2 v hv omega
maxcut_strong_deviation_carrier- If τ is a strong deviation from σ by a set S, then the set of vertices that actually change color, {v | τ v ≠ σ v}, also forms a valid strong deviation.
le_trans- If a ≤ b and b ≤ c, then a ≤ c.
Finset.card_le_card- If s ⊆ t for finite sets s and t, then the cardinality of s is at most the cardinality of t.
maxcut_utility_add_monochromatic_card- For any vertex v under coloring σ, the cut utility of v plus the number of its monochromatic neighbors equals the degree of v.
- The proof uses `maxcut_strong_deviation_carrier` to replace an arbitrary deviating coalition S with the exact support D = {v | τ v ≠ σ v} of color changes, ensuring that every vertex in D strictly benefits and actually changed color.
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.
theorem maxcut_strong_equilibrium_of_ranked_neighbors {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ : V → Fin k) (r : V → ℕ) (hlock : ∀ v c, c ≠ σ v → (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card ≤ (Finset.univ.filter fun w => G.Adj v w ∧ r w < r v ∧ σ w = c).card) : is_maxcut_strong_equilibrium G σ := by classical intro S τ hdev have hcarrier := maxcut_strong_deviation_carrier G σ τ S hdev let D := Finset.univ.filter fun v => τ v ≠ σ v obtain ⟨v, hv, hmin⟩ := D.exists_min_image r hcarrier.1 have hvdiff : τ v ≠ σ v := (Finset.mem_filter.mp hv).2 have hfixed : ∀ w, r w < r v → τ w = σ w := by intro w hw by_contra hne have hwD : w ∈ D := Finset.mem_filter.mpr ⟨Finset.mem_univ _, hne⟩ have := hmin w hwD omega have hsubset : (Finset.univ.filter fun w => G.Adj v w ∧ r w < r v ∧ σ w = τ v) ⊆ (Finset.univ.filter fun w => G.Adj v w ∧ τ w = τ v) := by intro w hw obtain ⟨_, hadj, hlt, hcolor⟩ := Finset.mem_filter.mp hw exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, hadj, by rw [hfixed w hlt, hcolor]⟩ have hmono := le_trans (hlock v (τ v) hvdiff) (Finset.card_le_card hsubset) have hσ := maxcut_utility_add_monochromatic_card G σ v have hτ := maxcut_utility_add_monochromatic_card G τ v have hgain := hcarrier.2.2 v hv omega