is_maxcut_strong_deviation
def
A 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 ∈ S. (The paper also asks every member to change color; it notes this is without loss of generality, and the resulting notion of strong equilibrium is the same.)
Statement
def is_maxcut_strong_deviation {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ : V → Fin k) (S : Finset V) (τ : V → Fin k) : Prop
- Defined in
- arXiv:2610.04948 (Social Optimality Does Not Imply Coalitional Stability in Unweighted Max-k-Cut Games), Sec. 1; the Lean version does not require every member to change color, which the paper notes is without loss of generality
- 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 50
- 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_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_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_five_cycle_repeatsAny five colorings that form a directed cycle of strong deviations repeat periodically to yield an infinite strong-deviation sequence…
- maxcut_unweighted_strong_deviation_cycle_existsThere is an unweighted simple graph on 46 vertices and an infinite sequence of three-color profiles that returns to its starting profile…
- 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_unweighted_minimal_deviation_cycle_existsOn the specified unweighted 71-vertex graph there is an infinite three-color strong-deviation sequence returning after 33 steps, and every…
- 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_witnessA specified three-color profile on the nine-vertex graph has utility at least four for every vertex and admits no profitable singleton…
- 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_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_cycle71_first_deviation_minimalThe 32 core vertices have a profitable deviation from the first displayed profile to the second, and no proper subcoalition can profitably…
- 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_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_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_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_cycle71_minimal_cycle_stepsEvery successive pair of the 33 profiles forms a strong deviation, and no proper subcoalition of its changing vertices has a profitable…
- maxcut_strong_deviation_cast_colorsInjectively embedding the available colors into a larger color set preserves a given strong deviation and its coalition.
- maxcut_fair9_normalized_certificatesFor every three-color profile on the nine-vertex graph whose first vertex has color zero, if all utilities are at least four and no…
- maxcut_fair9_deviationThe target profile is a strong deviation from the source profile using exactly the vertices whose colors change.
- 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_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_defect_one_strong_deviation_mono_decreasesA strong deviation from a coloring with at most one same-colored neighbor per vertex cannot create a monochromatic edge and must remove at…
- 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_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_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_cycle71_return_stepsEvery one of the 32 successive restoration moves, including the wraparound, is a profitable deviation by the displayed single vertex and…
- maxcut_strong_deviation_top_three_constantOn the triangle with three colors, from the constant coloring the coalition of two vertices that recolor to the two other colors is a…
- 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_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_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…
- is_maxcut_strong_equilibriumA coloring σ is a strong equilibrium of the Max-k-Cut game if no coalition has a strong deviation from it.
- maxcut_one_double_defect_new_edge_uniqueUnder a strong deviation from a profile with maximum defect two and at most one defect-two vertex, all newly monochromatic edges coincide…
- maxcut_optimal_deviation_two_outsidersAny strong deviation from a welfare-optimal coloring leaves at least two players outside its coalition.
- 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_strong_deviation_carrierEvery strong deviation contains a carrier deviation: the subset of players who actually change color forms a valid strong deviation.
- 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_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_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_cycle46_deviationsEach successive pair of the five displayed colorings, including the transition from the fifth to the first, is a strong deviation on the…
Lean source view module on GitHub
/-- A strong deviation from `σ` in the Max-k-Cut game: a nonempty coalition `S` and a coloring `τ` that agrees with `σ` outside `S` and strictly raises the utility of every member of `S`. -/ def is_maxcut_strong_deviation {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ : V → Fin k) (S : Finset V) (τ : V → Fin k) : Prop := S.Nonempty ∧ (∀ v, v ∉ S → τ v = σ v) ∧ ∀ v ∈ S, maxcut_utility G σ v < maxcut_utility G τ v