maxcut_welfare_split
For any set S of players, the welfare of a coloring is A + 2B + C, where A counts bichromatic adjacent ordered pairs inside S, B those from S to its complement, and C those inside the complement.
Statement
theorem maxcut_welfare_split {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (ρ : V → Fin k) (S : Finset V) : maxcut_welfare G ρ = ∑ v ∈ S, ∑ w ∈ S, (if G.Adj v w ∧ ρ w ≠ ρ v then 1 else 0 : ℕ) + 2 * ∑ v ∈ S, ∑ w ∈ Sᶜ, (if G.Adj v w ∧ ρ w ≠ ρ v then 1 else 0 : ℕ) + ∑ v ∈ Sᶜ, ∑ w ∈ Sᶜ, (if G.Adj v w ∧ ρ w ≠ ρ v then 1 else 0 : ℕ)
- Source
- step towards maxcut_optimal_strong_of_degree_le (arXiv:2610.04948, Corollary 9)
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- maxcut_welfareThe social welfare of a coloring σ in the Max-k-Cut game: the sum over all players v of u_v(σ), equal to twice the cut value.
- maxcut_utility_eq_sumThe Max-k-Cut utility of v is the sum over all w of the indicator that w is a neighbour of v with a different color.
- maxcut_pair_sum_commThe number of bichromatic adjacent ordered pairs (v, w) with v in S and w in T equals the number with v in T and w in S.
- Used by 8
- maxcut_deviation_cross_mono_riseLet σ be an optimal colouring of the unweighted Max-k-Cut game on a finite simple graph G and let (S,τ) be a strong deviation from σ. Then…
- maxcut_defect_two_deviation_welfare_nondecreasingA strong deviation cannot decrease the cut value when every member of the deviating coalition initially has at most two same-colored…
- maxcut_optimal_no_clique_deviationIn the unweighted Max-k-Cut game on a finite simple graph, no coalition that induces a clique has a strong deviation from a…
- 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_deviation_mono_inside_dropLet σ be an optimal colouring of the unweighted Max-k-Cut game on a finite simple graph G and let (S,τ) be a strong deviation from σ. Then…
- maxcut_defect_two_equal_welfare_deviation_structureIf a strong deviation from coalition defect at most two preserves welfare, every deviator has defect two before and one after, every old…
- maxcut_optimal_strong_of_degree_leFor every k ≥ 1: on every finite simple graph whose maximum degree is at most 2k − 1, every optimal coloring of the unweighted Max-k-Cut…
- maxcut_optimal_same_color_leAt an optimal coloring σ of the Max-k-Cut game, for every vertex v and every color c, the number of neighbours of v with color σ(v) is at…
The proof, explained
The welfare of a coloring is the sum of vertex utilities, which counts all bichromatic directed edges across the graph. Partitioning the vertices into a set S and its complement Sᶜ decomposes this double sum into four blocks: pairs within S, pairs from S to Sᶜ, pairs from Sᶜ to S, and pairs within Sᶜ. Because adjacency in a simple graph and color inequality are both symmetric relations, the two cross-boundary sums are equal and combine to twice the sum of pairs from S to Sᶜ.
For each vertex v, the sum over all vertices of the bichromatic edge indicator equals the sum over S plus the sum over Sᶜ.
An auxiliary identity (hs) is established: for any vertex v, the sum over all w of the indicator that w is adjacent to v and has a different color splits into the sum over w ∈ S plus the sum over w ∈ Sᶜ. This follows by reversing Finset.sum_add_sum_compl, which partitions a sum over a finite domain into the sum over a subset and the sum over its complement.
uses
Finset.sum_add_sum_complhave hs : ∀ v, ∑ w, (if G.Adj v w ∧ ρ w ≠ ρ v then 1 else 0 : ℕ) = ∑ w ∈ S, (if G.Adj v w ∧ ρ w ≠ ρ v then 1 else 0 : ℕ) + ∑ w ∈ Sᶜ, (if G.Adj v w ∧ ρ w ≠ ρ v then 1 else 0 : ℕ) := fun v => (Finset.sum_add_sum_compl S _).symm
The total welfare is expressed as a double sum of indicators, with the outer sum partitioned into S and Sᶜ.
By definition, maxcut_welfare is the sum of maxcut_utility over all vertices v. Rewriting with maxcut_utility_eq_sum expresses each vertex's utility as the inner sum over all vertices w of the bichromatic adjacency indicator. Then, reversing Finset.sum_add_sum_compl partitions the outer sum over all vertices into the sum over v ∈ S plus the sum over v ∈ Sᶜ.
uses
maxcut_utility_eq_sum,Finset.sum_add_sum_complunfold maxcut_welfare simp only [maxcut_utility_eq_sum] rw [← Finset.sum_add_sum_compl S]
The welfare expands into four double sums corresponding to pairs in S × S, S × Sᶜ, Sᶜ × S, and Sᶜ × Sᶜ.
Applying the auxiliary identity hs replaces each inner sum over all vertices with the sum over S plus the sum over Sᶜ. Then Finset.sum_add_distrib distributes the outer summation over this addition, expanding the expression into four separate double sums over S × S, S × Sᶜ, Sᶜ × S, and Sᶜ × Sᶜ.
uses
Finset.sum_add_distribsimp only [hs, Finset.sum_add_distrib]The cross-term summing over Sᶜ × S equals the cross-term summing over S × Sᶜ.
By maxcut_pair_sum_comm, the double sum over pairs (v, w) ∈ Sᶜ × S equals the double sum over (v, w) ∈ S × Sᶜ, reflecting the symmetry of graph adjacency and color inequality.
uses
maxcut_pair_sum_commrw [maxcut_pair_sum_comm G ρ Sᶜ S]Combining the two identical cross-terms yields the required decomposition.
The two cross-boundary sums between S and Sᶜ are now identical terms, so their sum simplifies to 2 times the sum over S × Sᶜ. The ring tactic collects these terms and verifies that the rearranged expression matches the right-hand side.
ring
Finset.sum_add_sum_compl- For any finite set s and function f into an additive commutative monoid, the sum of f over s plus the sum of f over its complement sᶜ equals the sum of f over the entire type.
maxcut_utility_eq_sum- The utility of vertex v under coloring ρ is the sum over all vertices w of the indicator that w is adjacent to v and has a different color.
Finset.sum_add_distrib- The sum of a pointwise sum of two functions over a finite set equals the sum of the first function plus the sum of the second function.
maxcut_pair_sum_comm- For any subsets S and T of vertices, the sum of bichromatic adjacent ordered pairs over S × T equals the sum over T × S.
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_welfare_split {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (ρ : V → Fin k) (S : Finset V) : maxcut_welfare G ρ = ∑ v ∈ S, ∑ w ∈ S, (if G.Adj v w ∧ ρ w ≠ ρ v then 1 else 0 : ℕ) + 2 * ∑ v ∈ S, ∑ w ∈ Sᶜ, (if G.Adj v w ∧ ρ w ≠ ρ v then 1 else 0 : ℕ) + ∑ v ∈ Sᶜ, ∑ w ∈ Sᶜ, (if G.Adj v w ∧ ρ w ≠ ρ v then 1 else 0 : ℕ) := by have hs : ∀ v, ∑ w, (if G.Adj v w ∧ ρ w ≠ ρ v then 1 else 0 : ℕ) = ∑ w ∈ S, (if G.Adj v w ∧ ρ w ≠ ρ v then 1 else 0 : ℕ) + ∑ w ∈ Sᶜ, (if G.Adj v w ∧ ρ w ≠ ρ v then 1 else 0 : ℕ) := fun v => (Finset.sum_add_sum_compl S _).symm unfold maxcut_welfare simp only [maxcut_utility_eq_sum] rw [← Finset.sum_add_sum_compl S] simp only [hs, Finset.sum_add_distrib] rw [maxcut_pair_sum_comm G ρ Sᶜ S] ring