maxcut_welfare
def
The 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.
Statement
def maxcut_welfare {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ : V → Fin k) : ℕ
- Defined in
- arXiv:2610.04948 (Social Optimality Does Not Imply Coalitional Stability in Unweighted Max-k-Cut Games), Sec. 1
- Verified
- 06 Oct 2026
- Axioms
- none listed
- 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 24
- maxcut_op89_exists_of_card_le_two_mul_add_oneFor every integer k ≥ 3 and every finite simple graph G on at most 2k+1 vertices, the unweighted Max-k-Cut game on (G,k) admits an optimal…
- maxcut_defect_two_nash_equal_cut_escapeA defect-two Nash coloring can have a strong deviation of equal welfare to a coloring of defect at least four.
- 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…
- is_maxcut_optimalA coloring σ is optimal if no coloring τ : V → [k] has larger social welfare (equivalently, σ is a maximum k-cut).
- 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_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_welfare_splitFor 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…
- 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_one_double_defect_strict_welfareIf a profile has maximum monochromatic degree two and at most one vertex of degree two, every strong deviation strictly increases social…
- maxcut_pinned_twins_displayed_deviationThe pinned-twin graph has an initial coloring of welfare 16376 and a strong deviation consisting of all 32 core twins to the doubled…
- 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_of_proper_coloringA proper k-colouring of a finite simple graph is a maximum k-cut of the Max-k-Cut game: it cuts every edge, so each player's utility…
- maxcut_one_double_defect_deviation_decreasesIf a coloring has monochromatic degree at most two with at most one vertex of degree two, every strong deviation stays in that class and…
- maxcut_defect_two_nash_to_nash_equal_cut_escapeA defect-two Nash coloring can strongly deviate at equal welfare to another Nash coloring of defect at least four.
- maxcut_op89_exists_of_max_degree_leFor every integer k ≥ 3 and every finite simple graph G whose maximum degree is at most 2k - 1, the unweighted Max-k-Cut game admits an…
- maxcut_defect_one_coloring_without_optimal_defect_oneThe eight-vertex graph has a defect-one three-coloring but no optimal three-coloring has defect one.
- maxcut_optimal_deviation_two_outsidersAny strong deviation from a welfare-optimal coloring leaves at least two players outside its coalition.
- maxcut_anchor_neutral_pivot_initial_optimalThe initial profile remains globally optimal after the extra edge is added.
- maxcut_pinned_twins_optimum_rigidityEvery welfare-maximizing 3-coloring ρ of the 182-vertex pinned twins graph maxcut_pinned_twins_graph is, up to one global permutation p of…
- maxcut_strong_equilibrium_exists_of_card_leFor every k ≥ 1 and every finite simple graph on at most 2k vertices, the Max-k-Cut game has an optimal coloring that is a strong…
- 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.
- maxcut_welfare_top_three_rainbowOn the triangle, the coloring with three distinct colors has social welfare 6 (all three edges cut, each counted twice).
Lean source view module on GitHub
/-- Social welfare of a coloring in the unweighted Max-k-Cut game: the sum of the players' utilities, which is twice the number of bichromatic edges. -/ def maxcut_welfare {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ : V → Fin k) : ℕ := ∑ v, maxcut_utility G σ v