maxcut_strong_equilibrium_of_one_double_defect
theoremverified
If 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 strong equilibrium with the same property.
Statement
theorem maxcut_strong_equilibrium_of_one_double_defect {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (h : ∃ σ : V → Fin k, (∀ v : V, (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card ≤ 2) ∧ ∀ u v : V, (Finset.univ.filter fun w => G.Adj u w ∧ σ w = σ u).card = 2 → (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card = 2 → u = v) : ∃ σ : V → Fin k, is_maxcut_strong_equilibrium G σ ∧ (∀ v : V, (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card ≤ 2) ∧ (∀ u v : V, (Finset.univ.filter fun w => G.Adj u w ∧ σ w = σ u).card = 2 → (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card = 2 → u = v)
- Source
- Structural potential argument for the strong-equilibrium existence question OP-85; experiment 16416.
- Verified
- 06 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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…
- is_maxcut_strong_equilibriumA coloring σ is a strong equilibrium of the Max-k-Cut game if no coalition has a strong deviation from it.
- 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 1
- 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…
Lean source view module on GitHub
set_option maxRecDepth 8192 set_option maxHeartbeats 3000000 theorem maxcut_strong_equilibrium_of_one_double_defect {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (h : ∃ σ : V → Fin k, (∀ v : V, (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card ≤ 2) ∧ ∀ u v : V, (Finset.univ.filter fun w => G.Adj u w ∧ σ w = σ u).card = 2 → (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card = 2 → u = v) : ∃ σ : V → Fin k, is_maxcut_strong_equilibrium G σ ∧ (∀ v : V, (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card ≤ 2) ∧ (∀ u v : V, (Finset.univ.filter fun w => G.Adj u w ∧ σ w = σ u).card = 2 → (Finset.univ.filter fun w => G.Adj v w ∧ σ w = σ v).card = 2 → u = v) := by classical let M (ρ : V → Fin k) (v : V) : Finset V := Finset.univ.filter fun w => G.Adj v w ∧ ρ w = ρ v let score (ρ : V → Fin k) : ℕ := ∑ v : V, (M ρ v).card let A : Finset (V → Fin k) := Finset.univ.filter fun ρ => (∀ v, (M ρ v).card ≤ 2) ∧ ∀ u v, (M ρ u).card = 2 → (M ρ v).card = 2 → u = v obtain ⟨ρ, hρ⟩ := h have hA : A.Nonempty := by refine ⟨ρ, Finset.mem_filter.mpr ⟨Finset.mem_univ _, ?_⟩⟩ exact hρ obtain ⟨σ, hσA, hmin⟩ := Finset.exists_min_image A score hA have hσ : (∀ v, (M σ v).card ≤ 2) ∧ (∀ u v, (M σ u).card = 2 → (M σ v).card = 2 → u = v) := (Finset.mem_filter.mp hσA).2 refine ⟨σ, ?_, hσ.1, hσ.2⟩ intro C τ hdev have hd := maxcut_one_double_defect_deviation_decreases G σ τ C hσ.1 hσ.2 hdev have hτA : τ ∈ A := Finset.mem_filter.mpr ⟨Finset.mem_univ _, hd.2⟩ have hs : score τ < score σ := hd.1 have hm := hmin τ hτA omega