AFTD Auto-Formalizing Theoretical Domains

maxcut_strong_equilibrium_of_ranked_neighbors

theoremverified

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

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.

  1. 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.

    lines 8–10

    uses maxcut_strong_deviation_carrier

      classical
      intro S τ hdev
      have hcarrier := maxcut_strong_deviation_carrier G σ τ S hdev
  2. 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).

    lines 11–13

      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
  3. 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).

    lines 14–19

      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
  4. 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).

    lines 20–24

      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]⟩
  5. 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.

    line 25

    uses le_trans, Finset.card_le_card

      have hmono := le_trans (hlock v (τ v) hvdiff) (Finset.card_le_card hsubset)
  6. 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.

    lines 26–29

    uses maxcut_utility_add_monochromatic_card

      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
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.

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

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
See it in the graphDiscuss this resultChallenge it