is_maxcut_optimal
def
A coloring σ is optimal if no coloring τ : V → [k] has larger social welfare (equivalently, σ is a maximum k-cut).
Statement
def is_maxcut_optimal {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ : V → Fin k) : Prop
- 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_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.
- Used by 26
- 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_optimal_strong_of_internal_mono_ltIf σ is an optimal colouring of the unweighted Max-k-Cut game on a finite simple graph G and every nonempty set S of vertices carries…
- 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_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_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_op89_exists_of_colorableIf a finite simple graph admits a proper k-colouring, then the unweighted Max-k-Cut game on (G,k) has an optimal colouring that is a…
- maxcut_complete_graph_optimal_balancedIn an optimal k-colouring of the complete graph K_n, any two colour classes differ in size by at most one: a vertex whose class has a…
- maxcut_complete_graph_optimal_strongEvery optimal k-colouring of the complete graph K_n is a strong equilibrium of the Max-k-Cut game, so no coalition can strictly raise all…
- 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_optimal_top_three_rainbowOn the triangle with three colors, the rainbow coloring is optimal.
- 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_optimal_strong_up_to_degreeFor k and D: on every finite simple graph of maximum degree at most D, every optimal coloring of the Max-k-Cut game with k colors is a…
- maxcut_optimal_strong_of_color_unusedIf σ is an optimal colouring of the unweighted Max-k-Cut game on a finite simple graph G and some colour c is never used by σ, then σ is a…
- 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_deviation_degree_sum_geLet σ 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_one_coloring_without_optimal_defect_oneThe eight-vertex graph has a defect-one three-coloring but no optimal three-coloring has defect one.
- maxcut_has_optimal_strong_equilibriumIn the unweighted Max-k-Cut game on a finite simple graph G with k colors, there exists an optimal coloring σ : V → Fin k that is also a…
- maxcut_optimal_deviation_two_outsidersAny strong deviation from a welfare-optimal coloring leaves at least two players outside its coalition.
- maxcut_strong_equilibrium_reduce_dense_coreFix k at least three. If every finite graph of minimum degree at least k, with preconnected vertex deletions and with some vertex of…
- 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_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…
- maxcut_deviation_internal_color_count_ltLet σ 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_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.
Lean source view module on GitHub
/-- An optimal coloring of the Max-k-Cut game: it maximizes social welfare (equivalently the cut value) over all colorings `V → Fin k`. -/ def is_maxcut_optimal {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ : V → Fin k) : Prop := ∀ τ : V → Fin k, maxcut_welfare G τ ≤ maxcut_welfare G σ