maxcut_three_leaf_star_no_fixed_profile_extension
theoremverified
The identity three-coloring is a strong equilibrium on three isolated vertices, but restoring a new center adjacent to all three cannot extend that same profile to a strong equilibrium using any of the three colors.
Statement
theorem maxcut_three_leaf_star_no_fixed_profile_extension :
is_maxcut_strong_equilibrium (⊥ : SimpleGraph (Fin 3)) (id : Fin 3 → Fin 3) ∧
∀ c : Fin 3, ¬ is_maxcut_strong_equilibrium maxcut_three_leaf_star_graph (Fin.cases c id)- Source
- Finite obstruction computed in experiment 16369.
- Verified
- 06 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- maxcut_three_leaf_star_graphThe three-leaf star, with vertex zero at the center.
- 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_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)…
- 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…
Lean source view module on GitHub
set_option maxRecDepth 100000 set_option maxHeartbeats 12000000 instance : DecidableRel maxcut_three_leaf_star_graph.Adj := by unfold maxcut_three_leaf_star_graph infer_instance theorem maxcut_three_leaf_star_no_fixed_profile_extension : is_maxcut_strong_equilibrium (⊥ : SimpleGraph (Fin 3)) (id : Fin 3 → Fin 3) ∧ ∀ c : Fin 3, ¬ is_maxcut_strong_equilibrium maxcut_three_leaf_star_graph (Fin.cases c id) := by unfold is_maxcut_strong_equilibrium is_maxcut_strong_deviation maxcut_utility decide