maxcut_cycle71_first_deviation_minimal
theoremverified
The 32 core vertices have a profitable deviation from the first displayed profile to the second, and no proper subcoalition can profitably deviate from the first profile using any alternative coloring.
Statement
theorem maxcut_cycle71_first_deviation_minimal : @is_maxcut_strong_deviation _ _ maxcut_cycle71_graph (by intro u v; unfold maxcut_cycle71_graph maxcut_cycle71_field SimpleGraph.fromRel; infer_instance) 3 (maxcut_cycle71_coloring 0) (Finset.univ.filter fun v : Fin 71 => v.val < 32) (maxcut_cycle71_coloring 1) ∧ ∀ S : Finset (Fin 71), S ⊂ (Finset.univ.filter fun v : Fin 71 => v.val < 32) → ¬ ∃ τ : Fin 71 → Fin 3, @is_maxcut_strong_deviation _ _ maxcut_cycle71_graph (by intro u v; unfold maxcut_cycle71_graph maxcut_cycle71_field SimpleGraph.fromRel; infer_instance) 3 (maxcut_cycle71_coloring 0) S τ
- Source
- Explicit regular 71-vertex construction for the unweighted minimal-deviation cycle, supported by experiments 12443, 12444, 12450 and 12452.
- Verified
- 02 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- maxcut_cycle71_graphThe explicit 71-vertex finite simple graph with four core blocks of eight and three anchor blocks of thirteen, with edges determined by…
- maxcut_cycle71_coloringFive displayed three-color profiles on the regular 71-vertex construction, with anchor colors fixed and four core blocks recolored in…
- 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…
- maxcut_cycle71_force_closed_coreAny nonempty set of core vertices closed under adjacent vertices whose initial color is the first vertex’s deviation color contains all 32…
- maxcut_cycle71_fieldThe number of anchor neighbors of each fixed color assigned to each core block in the regular 71-vertex construction.
- 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 2
- 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_anchor_neutral_pivot_initial_strongThe displayed initial profile is a strong equilibrium after the extra edge is added.
The proof, explained
This proof shows that the coalition of 32 core vertices has a profitable strong deviation from the initial coloring to the next coloring, and no strictly smaller subcoalition can profitably deviate.
test claim
test explanation
refine ⟨?_, ?_⟩ · unfold is_maxcut_strong_deviation maxcut_utility decide +kernel · exact mc71_minimal_aux _
- Unresolved check: no step explains line(s) 8, 9, 10, 11, 12, 13, 14, 15, 23, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35 -- every tactic of the proof has to belong to some step
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Outside a set `P` closed under the coalition, a deviator's utility counts at most theneighbours in `P` and those whose old color differs from its new one. -/theorem mc71_utility_le_filter {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ τ : V → Fin k) (S : Finset V) (hout : ∀ x, x ∉ S → τ x = σ x) (P : V → Prop) [DecidablePred P] (hP : ∀ x ∈ S, P x) (v : V) : maxcut_utility G τ v ≤ (Finset.univ.filter fun x => G.Adj v x ∧ (P x ∨ σ x ≠ τ v)).card := by unfold maxcut_utility apply Finset.card_le_card intro x hx simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hx ⊢ refine ⟨hx.1, ?_⟩ by_cases hxS : x ∈ S · exact Or.inl (hP x hxS) · exact Or.inr (by rw [← hout x hxS]; exact hx.2)theorem mc71_utility_le_filter_erase {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (σ τ : V → Fin k) (S : Finset V) (hout : ∀ x, x ∉ S → τ x = σ x) (P : V → Prop) [DecidablePred P] (hP : ∀ x ∈ S, P x) (v w : V) (hw : G.Adj v w) (hPw : P w) (hτw : τ w = τ v) : maxcut_utility G τ v + 1 ≤ (Finset.univ.filter fun x => G.Adj v x ∧ (P x ∨ σ x ≠ τ v)).card := by have hsub : (Finset.univ.filter fun x => G.Adj v x ∧ τ x ≠ τ v) ⊆ (Finset.univ.filter fun x => G.Adj v x ∧ (P x ∨ σ x ≠ τ v)).erase w := by intro x hx simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_erase] at hx ⊢ refine ⟨?_, hx.1, ?_⟩ · rintro rfl; exact hx.2 hτw · by_cases hxS : x ∈ S · exact Or.inl (hP x hxS) · exact Or.inr (by rw [← hout x hxS]; exact hx.2) have hmem : w ∈ (Finset.univ.filter fun x => G.Adj v x ∧ (P x ∨ σ x ≠ τ v)) := by simp only [Finset.mem_filter, Finset.mem_univ, true_and]; exact ⟨hw, Or.inl hPw⟩ have := Finset.card_le_card hsub rw [Finset.card_erase_of_mem hmem] at this unfold maxcut_utility have h1 := Finset.card_pos.mpr ⟨w, hmem⟩ omega/-- The finite count: a core vertex moving to a new color `c` gains at most one over itsfirst-profile utility, even if every core neighbour cooperates, and gains nothing unless `c`is its second-profile color. -/theorem mc71_count_check [inst : DecidableRel maxcut_cycle71_graph.Adj] : ∀ v : Fin 71, v.val < 32 → ∀ c : Fin 3, c ≠ maxcut_cycle71_coloring 0 v → (Finset.univ.filter fun x => maxcut_cycle71_graph.Adj v x ∧ (x.val < 32 ∨ maxcut_cycle71_coloring 0 x ≠ c)).card ≤ maxcut_utility maxcut_cycle71_graph (maxcut_cycle71_coloring 0) v + (if c = maxcut_cycle71_coloring 1 v then 1 else 0) := by have e : inst = (show DecidableRel maxcut_cycle71_graph.Adj by intro u v; unfold maxcut_cycle71_graph maxcut_cycle71_field SimpleGraph.fromRel; infer_instance) := Subsingleton.elim _ _ subst e unfold maxcut_utility decide +kerneltheorem mc71_minimal_aux (inst : DecidableRel maxcut_cycle71_graph.Adj) : ∀ S : Finset (Fin 71), S ⊂ (Finset.univ.filter fun v : Fin 71 => v.val < 32) → ¬ ∃ τ : Fin 71 → Fin 3, is_maxcut_strong_deviation maxcut_cycle71_graph (maxcut_cycle71_coloring 0) S τ := by rintro S hS ⟨τ, hne, hout, himp⟩ have hcore : ∀ v ∈ S, v.val < 32 := by intro v hv have := hS.subset hv simpa using this have hMne : (S.filter fun v => τ v ≠ maxcut_cycle71_coloring 0 v).Nonempty := by by_contra hM rw [Finset.not_nonempty_iff_eq_empty, Finset.filter_eq_empty_iff] at hM have hτ : τ = maxcut_cycle71_coloring 0 := by funext x by_cases hx : x ∈ S · exact not_not.mp (hM hx) · exact hout x hx obtain ⟨v, hv⟩ := hne have := himp v hv rw [hτ] at this exact lt_irrefl _ this have hall := maxcut_cycle71_force_closed_core _ hMne (fun v hv => hcore v (Finset.mem_filter.mp hv).1) (by intro v hv w hw hadj hcol rw [Finset.mem_filter] at hv by_contra hwM have hτw : τ w = maxcut_cycle71_coloring 0 w := by by_cases hwS : w ∈ S · by_contra h; exact hwM (Finset.mem_filter.mpr ⟨hwS, h⟩) · exact hout w hwS have hlt := himp v hv.1 have hchk := mc71_count_check v (hcore v hv.1) (τ v) hv.2 have hP : ∀ x ∈ S, (fun x : Fin 71 => x.val < 32) x := hcore by_cases hc : τ v = maxcut_cycle71_coloring 1 v · have hb := mc71_utility_le_filter_erase maxcut_cycle71_graph (maxcut_cycle71_coloring 0) τ S hout (fun x : Fin 71 => x.val < 32) hP v w hadj hw (by rw [hτw, hcol, hc]) rw [if_pos hc] at hchk have h2 : maxcut_utility maxcut_cycle71_graph τ v + 1 ≤ maxcut_utility maxcut_cycle71_graph (maxcut_cycle71_coloring 0) v + 1 := le_trans hb hchk omega · have hb := mc71_utility_le_filter maxcut_cycle71_graph (maxcut_cycle71_coloring 0) τ S hout (fun x : Fin 71 => x.val < 32) hP v rw [if_neg hc] at hchk have h2 : maxcut_utility maxcut_cycle71_graph τ v ≤ maxcut_utility maxcut_cycle71_graph (maxcut_cycle71_coloring 0) v + 0 := le_trans hb hchk omega) apply hS.2 intro w hw have hw' : w.val < 32 := by simpa using hw exact (Finset.mem_filter.mp (hall w hw')).1theorem maxcut_cycle71_first_deviation_minimal : @is_maxcut_strong_deviation _ _ maxcut_cycle71_graph (by intro u v; unfold maxcut_cycle71_graph maxcut_cycle71_field SimpleGraph.fromRel; infer_instance) 3 (maxcut_cycle71_coloring 0) (Finset.univ.filter fun v : Fin 71 => v.val < 32) (maxcut_cycle71_coloring 1) ∧ ∀ S : Finset (Fin 71), S ⊂ (Finset.univ.filter fun v : Fin 71 => v.val < 32) → ¬ ∃ τ : Fin 71 → Fin 3, @is_maxcut_strong_deviation _ _ maxcut_cycle71_graph (by intro u v; unfold maxcut_cycle71_graph maxcut_cycle71_field SimpleGraph.fromRel; infer_instance) 3 (maxcut_cycle71_coloring 0) S τ := by refine ⟨?_, ?_⟩ · unfold is_maxcut_strong_deviation maxcut_utility decide +kernel · exact mc71_minimal_aux _