is_maxcut_strong_equilibrium
def
A coloring σ is a strong equilibrium of the Max-k-Cut game if no coalition has a strong deviation from it.
Statement
def is_maxcut_strong_equilibrium {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
- 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…
- Used by 39
- 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_fair9_stable_exampleA specified three-color profile is a strong equilibrium of the nine-vertex graph.
- maxcut_fair9_nash_fairness_obstructionOn the specified nine-vertex three-color graph there is a singleton-stable profile with every utility at least four, no strong equilibrium…
- 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_strong_equilibrium_reduce_vertex_deletionsFix k. If every finite graph whose every vertex deletion is preconnected has a strong k-color equilibrium, then every finite graph has a…
- maxcut_neutral_pivot_safe_not_necessaryA full graph and its vertex deletion may both be strongly stable, with exactly one restored-vertex conflict, while that conflict neighbor…
- maxcut_strong_equilibrium_color_permutationA global permutation of colors maps a strong equilibrium to a strong equilibrium.
- maxcut_strong_equilibrium_of_near_defect_oneIf deleting a vertex produces a graph admitting a defect-one k-coloring and the deleted vertex has degree below 2k, then the original…
- 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_strong_equilibrium_of_defect_oneIf a finite unweighted graph admits a k-coloring in which each vertex has at most one same-colored neighbor, it admits a strong k-color…
- maxcut_defect_one_dense_core_witnessA 12-vertex graph of minimum degree nine has a six-clique, a 1-defective 3-coloring, and a strong 3-color equilibrium.
- 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_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_fair9_no_maxmin_strong_nashOn the specified nine-vertex graph, no strong equilibrium has minimum utility at least that of every singleton-stable three-coloring.
- maxcut_single_vertex_sum_strong_equilibriumIf a finite graph is covered by two induced subgraphs meeting in one vertex with no edge between their exclusive parts, and a coloring…
- maxcut_three_leaf_star_no_fixed_profile_extensionThe identity three-coloring is a strong equilibrium on three isolated vertices, but restoring a new center adjacent to all three cannot…
- maxcut_optimal_not_strong_degree_66There is a finite simple graph of maximum degree at most 66 with an optimal coloring of the Max-3-Cut game that is not a strong…
- maxcut_strong_equilibrium_reduce_connected_coreFix k. If every finite graph of minimum degree at least k whose every vertex deletion is preconnected has a strong k-color equilibrium,…
- maxcut_strong_equilibrium_of_ranked_neighborsA coloring is a strong equilibrium if, for every alternative color at each vertex, the earlier-ranked neighbors of that color number at…
- 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_anchor_three_coloring_strongThe displayed post-deviation coloring tau is a strong equilibrium on the paper’s explicit graph G_3. This theorem proves stability only;…
- 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_strong_equilibrium_extend_low_degree_vertexIf a vertex has degree strictly smaller than the number k of available colors, a strong equilibrium of the induced graph obtained by…
- maxcut_nash_extension_with_profitable_pivot_coalitionA best-responding one-conflict vertex can extend a strong deletion equilibrium to a Nash profile that is not strongly stable. A two-vertex…
- maxcut_strong_equilibrium_reduce_single_vertex_sumsFor any fixed number of colors, if every finite graph with decidable equality and adjacency that has no nontrivial separation into two…
- 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_strong_equilibrium_extension_of_colorable_deletionIf a vertex has degree below twice the number of colors and its deletion is k-colorable, then the original graph has a strong equilibrium…
- 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_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_strongThe displayed initial profile is a strong equilibrium after the extra edge is added.
- maxcut_strong_equilibrium_of_proper_coloringA proper k-colouring of a finite simple graph is a strong equilibrium of the Max-k-Cut game: every player already has utility equal to its…
- 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_strong_equilibrium_of_saturated_vertexA coloring of a finite graph is a strong equilibrium if its restriction after deleting a vertex is a strong equilibrium and every edge…
- maxcut_not_strong_equilibrium_top_three_constantOn the triangle with three colors, the constant coloring is not a strong equilibrium.
- maxcut_strong_equilibrium_of_one_double_defectIf a graph admits a k-coloring in which every vertex has at most two same-colored neighbors and at most one vertex has two, it has a…
- 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_unused_color_or_safe_pivot_of_proper_coloringIf a finite graph admits a proper k-coloring and N has fewer than 2k vertices, there is a strong equilibrium with an unused color on N or…
Lean source view module on GitHub
/-- A strong equilibrium of the Max-k-Cut game: a coloring admitting no strong deviation. -/ def is_maxcut_strong_equilibrium {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ : V → Fin k) : Prop := ∀ (S : Finset V) (τ : V → Fin k), ¬ is_maxcut_strong_deviation G σ S τ