maxcut_strong_deviation_carrier
Every strong deviation contains a carrier deviation: the subset of players who actually change color forms a valid strong deviation.
Statement
theorem maxcut_strong_deviation_carrier {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ τ : V → Fin k) (S : Finset V) (hdev : is_maxcut_strong_deviation G σ S τ) : is_maxcut_strong_deviation G σ (Finset.univ.filter fun v => τ v ≠ σ v) τ
- Source
- step towards maxcut_game_strong_equilibrium_exists
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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 2
- maxcut_two_color_strong_equilibrium_restricts_vertexFor every finite graph and every vertex, a strong two-color equilibrium exists whose restriction after deleting that vertex is also…
- maxcut_strong_equilibrium_of_ranked_neighborsA coloring is a strong equilibrium if, for every alternative color at each vertex, the earlier-ranked neighbors of that color number at…
The proof, explained
To prove that the carrier set of players who actually change color forms a valid strong deviation, the proof verifies the three defining conditions of a strong deviation. First, any player who changes color must belong to the original deviation set S, so every member of the carrier set inherits a strict utility increase from S. Second, the carrier set cannot be empty, because if no player changed color, the strategy profile would remain unchanged, contradicting the strict utility gain guaranteed for members of the nonempty set S. Finally, by construction, players outside the carrier set do not change color.
Extract the three components of the strong deviation hypothesis for S.
By definition, the hypothesis that S forms a strong deviation from σ to τ provides three facts: S is nonempty (`hne`), players outside S do not change strategy (`hout`, so τ v = σ v for all v ∉ S), and every player in S strictly increases their utility (`hgain`).
classical obtain ⟨hne, hout, hgain⟩ := hdevAny player whose color changes must belong to S.
Suppose for contradiction that a player v satisfies τ v ≠ σ v but does not belong to S. By `hout`, every player outside S must satisfy τ v = σ v, directly contradicting τ v ≠ σ v.
have hsub : ∀ v, τ v ≠ σ v → v ∈ S := by intro v hv by_contra hn exact hv (hout v hn)
At least one player changes color between σ and τ.
Assume for contradiction that no player changes color. Then τ v = σ v for every vertex v, which by function extensionality means τ = σ. But S is nonempty, so we can pick some v ∈ S. By `hgain`, v strictly improves its utility from σ to τ; substituting τ = σ would mean the utility of v under σ is strictly less than itself, which is impossible.
uses
not_exists.mphave hdiff : ∃ v, τ v ≠ σ v := by by_contra h have heq : τ = σ := funext fun v => by simpa using not_exists.mp h v obtain ⟨v, hv⟩ := hne have := hgain v hv simpa [heq] using this
The carrier set of players who change color is nonempty.
We split the goal of showing that the carrier set {v | τ v ≠ σ v} is a strong deviation into its three defining conditions. For the first condition, the witness produced in the previous step guarantees that the carrier set has at least one element.
refine ⟨?_, ?_, ?_⟩ · obtain ⟨v, hv⟩ := hdiff exact ⟨v, by simp [hv]⟩
Players outside the carrier set do not change color.
If a vertex v is not in {w | τ w ≠ σ w}, then the negation ¬(τ v ≠ σ v) holds, which simplifies directly to τ v = σ v.
· intro v hv simpa using hv
Every player in the carrier set strictly increases their utility.
Let v be in the carrier set, so τ v ≠ σ v. By the earlier lemma that any vertex with changed color belongs to S, v must belong to S. Therefore, the utility gain condition for S applies, showing that v strictly improves its utility from σ to τ.
uses
Finset.mem_filter.mp· intro v hv exact hgain v (hsub v (Finset.mem_filter.mp hv).2)
not_exists.mp- If there does not exist an element satisfying a predicate, then every element satisfies the negation of that predicate.
Finset.mem_filter.mp- An element belongs to `Finset.filter p s` if and only if it belongs to `s` and satisfies `p`.
- The carrier set is represented formally as `Finset.univ.filter (fun v => τ v ≠ σ v)`, relying on classical decidability to filter the universe of vertices by inequality.
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.
/-- Every strong deviation contains a carrier deviation: the subset of players who actually change color forms a valid strong deviation. -/theorem maxcut_strong_deviation_carrier {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ τ : V → Fin k) (S : Finset V) (hdev : is_maxcut_strong_deviation G σ S τ) : is_maxcut_strong_deviation G σ (Finset.univ.filter fun v => τ v ≠ σ v) τ := by classical obtain ⟨hne, hout, hgain⟩ := hdev have hsub : ∀ v, τ v ≠ σ v → v ∈ S := by intro v hv by_contra hn exact hv (hout v hn) have hdiff : ∃ v, τ v ≠ σ v := by by_contra h have heq : τ = σ := funext fun v => by simpa using not_exists.mp h v obtain ⟨v, hv⟩ := hne have := hgain v hv simpa [heq] using this refine ⟨?_, ?_, ?_⟩ · obtain ⟨v, hv⟩ := hdiff exact ⟨v, by simp [hv]⟩ · intro v hv simpa using hv · intro v hv exact hgain v (hsub v (Finset.mem_filter.mp hv).2)