maxcut_strong_equilibrium_color_permutation
A global permutation of colors maps a strong equilibrium to a strong equilibrium.
Statement
theorem maxcut_strong_equilibrium_color_permutation {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ : V → Fin k) (p : Equiv.Perm (Fin k)) (h : is_maxcut_strong_equilibrium G σ) : is_maxcut_strong_equilibrium G (fun v => p (σ v))
- Source
- Structural reduction for OP-85, the strong-equilibrium existence problem; the two-piece gluing step is maxcut_single_vertex_sum_strong_equilibrium.
- Verified
- 03 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- maxcut_utility_color_permutationPermuting all color labels preserves every player’s utility in the Max-k-Cut game.
- 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 2
- maxcut_single_vertex_sum_strong_equilibrium_existsFor two induced subgraphs covering a finite graph, meeting in exactly one vertex, with no edges between their exclusive parts, strong…
- 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
Suppose for contradiction that the permuted coloring $p \circ \sigma$ is not a strong equilibrium, so some coalition $S$ has a profitable deviation $\tau$. By pulling $\tau$ back through the inverse permutation $p^{-1}$, coalition $S$ would also have a profitable deviation $p^{-1} \circ \tau$ from the original coloring $\sigma$. Because Max-Cut utility depends solely on whether adjacent vertices have different colors, it is invariant under color permutations, ensuring that the utility gains under $\tau$ over $p \circ \sigma$ match those under $p^{-1} \circ \tau$ over $\sigma$. This shows that $p^{-1} \circ \tau$ is a valid strong deviation from $\sigma$, contradicting the assumption that $\sigma$ is a strong equilibrium.
To derive a contradiction, it suffices to show that the pulled-back coloring $p^{-1} \circ \tau$ is a strong deviation from $\sigma$ for coalition $S$, which reduces to showing that $p^{-1} \circ \tau$ agrees with $\sigma$ outside $S$ and strictly increases utility on $S$.
We assume for contradiction that the permuted coloring $p \circ \sigma$ admits a strong deviation $\tau$ by a coalition $S$ (line 5). Since $\sigma$ is assumed to be a strong equilibrium, applying this hypothesis to $S$ and the pulled-back strategy $p^{-1} \circ \tau$ leaves the goal of proving that $(S, p^{-1} \circ \tau)$ would be a strong deviation from $\sigma$ (line 6). Because $S$ is already known to be nonempty from the deviation $\tau$, this requirement decomposes into two obligations: verifying that vertices outside $S$ keep their original colors, and that vertices in $S$ strictly improve their utility (line 7).
intro S τ hd apply h S (fun v => p.symm (τ v)) refine ⟨hd.1, ?_, ?_⟩
For every vertex $v \notin S$, the pulled-back coloring satisfies $(p^{-1} \circ \tau)(v) = \sigma(v)$.
Let $v \notin S$ (line 8). We need to show that $p^{-1}(\tau(v)) = \sigma(v)$ (line 9). Because $\tau$ is a deviation on $S$, it does not alter vertices outside $S$, meaning $\tau(v) = p(\sigma(v))$ (line 10). Applying $p^{-1}$ to both sides then yields $p^{-1}(p(\sigma(v))) = \sigma(v)$ by `p.symm_apply_apply` (line 11).
uses
p.symm_apply_apply· intro v hv change p.symm (τ v) = σ v rw [hd.2.1 v hv] exact p.symm_apply_apply (σ v)
For every vertex $v \in S$, the utility under $p^{-1} \circ \tau$ is strictly greater than under $\sigma$.
Let $v \in S$ (line 12). By assumption that $\tau$ is a profitable deviation from $p \circ \sigma$, the utility of $v$ strictly increases: $\text{maxcut\_utility}(G, p \circ \sigma, v) < \text{maxcut\_utility}(G, \tau, v)$ (line 13). By `maxcut_utility_color_permutation`, permuting the colors of $\sigma$ by $p$ does not change utilities, so $\text{maxcut\_utility}(G, \sigma, v) < \text{maxcut\_utility}(G, \tau, v)$ (line 14). Similarly, applying $p$ to $p^{-1} \circ \tau$ recovers $\tau$ via `Equiv.apply_symm_apply`, which establishes that $\text{maxcut\_utility}(G, \tau, v) = \text{maxcut\_utility}(G, p^{-1} \circ \tau, v)$ (lines 15–16). Rewriting the inequality with this equality yields $\text{maxcut\_utility}(G, \sigma, v) < \text{maxcut\_utility}(G, p^{-1} \circ \tau, v)$ (lines 17–18).
uses
maxcut_utility_color_permutation,Equiv.apply_symm_apply· intro v hv have hg := hd.2.2 v hv rw [maxcut_utility_color_permutation G σ p v] at hg have heq := maxcut_utility_color_permutation G (fun v => p.symm (τ v)) p v simp only [Equiv.apply_symm_apply] at heq rw [← heq] exact hg
p.symm_apply_apply- Applying a permutation and then its inverse yields the original element: $p^{-1}(p(x)) = x$.
maxcut_utility_color_permutation- The Max-Cut utility of a vertex is invariant under applying a global permutation to the color classes.
Equiv.apply_symm_apply- Applying an equivalence to the result of its inverse yields the original element: $e(e^{-1}(x)) = x$.
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_color_permutation {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ : V → Fin k) (p : Equiv.Perm (Fin k)) (h : is_maxcut_strong_equilibrium G σ) : is_maxcut_strong_equilibrium G (fun v => p (σ v)) := by intro S τ hd apply h S (fun v => p.symm (τ v)) refine ⟨hd.1, ?_, ?_⟩ · intro v hv change p.symm (τ v) = σ v rw [hd.2.1 v hv] exact p.symm_apply_apply (σ v) · intro v hv have hg := hd.2.2 v hv rw [maxcut_utility_color_permutation G σ p v] at hg have heq := maxcut_utility_color_permutation G (fun v => p.symm (τ v)) p v simp only [Equiv.apply_symm_apply] at heq rw [← heq] exact hg