maxcut_utility_color_permutation
Permuting all color labels preserves every player’s utility in the Max-k-Cut game.
Statement
theorem maxcut_utility_color_permutation {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ : V → Fin k) (p : Equiv.Perm (Fin k)) (v : V) : maxcut_utility G (fun w => p (σ w)) v = maxcut_utility G σ v
- Source
- Color-symmetry helper for the OP-89 pinned-twin refutation criterion.
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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 4
- maxcut_strong_equilibrium_color_permutationA global permutation of colors maps a strong equilibrium to a strong equilibrium.
- maxcut_pinned_twins_refutes_of_rigidityIf every optimum of the explicit pinned-twin graph is its displayed initial coloring up to a global color permutation, then this graph has…
- maxcut_fair9_no_strong_with_min_fourNo strong equilibrium of the nine-vertex graph with three colors gives every vertex utility at least four.
- 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.
The proof, explained
In the Max-k-Cut game, a vertex's utility is the number of its neighbors assigned a different color. Because any permutation of colors is a bijection, two vertices have distinct colors under the permuted coloring if and only if they have distinct colors under the original coloring. Consequently, the set of neighbors contributing to the utility of $v$ is unchanged, and its cardinality—the utility—is preserved.
It suffices to show that the set of neighbors of $v$ with a different color than $v$ under $p \circ \sigma$ equals the corresponding set under $\sigma$.
Unfolding the definition of `maxcut_utility`, the utility of $v$ is the cardinality of the finset of neighbors $w$ whose assigned color differs from that of $v$. By congruence (`congr 1`), equality of cardinalities reduces to proving that the two underlying sets of vertices are equal.
classical unfold maxcut_utility congr 1
The two sets of neighbors are equal, completing the proof.
By extensionality (`ext w`), the two sets are equal if an arbitrary vertex $w$ belongs to the first if and only if it belongs to the second. For both sets, membership requires that $w$ is adjacent to $v$ and that the color of $w$ differs from the color of $v$. Because $p$ is a permutation, it is injective, so $p(\sigma(w)) \neq p(\sigma(v))$ is logically equivalent to $\sigma(w) \neq \sigma(v)$. The `simp` tactic applies this equivalence to simplify the membership conditions, leaving identical propositions on both sides and closing the goal.
ext w simp
- Line 5 activates classical logic, allowing Lean to handle decidability in set comprehensions without explicit constructive proofs; this is standard formal bookkeeping with no counterpart on paper.
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_utility_color_permutation {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ : V → Fin k) (p : Equiv.Perm (Fin k)) (v : V) : maxcut_utility G (fun w => p (σ w)) v = maxcut_utility G σ v := by classical unfold maxcut_utility congr 1 ext w simp