AFTD Auto-Formalizing Theoretical Domains

maxcut_anchor_neutral_pivot_initial_optimal

theoremverified

The initial profile remains globally optimal after the extra edge is added.

Statement

theorem maxcut_anchor_neutral_pivot_initial_optimal : is_maxcut_optimal maxcut_anchor_neutral_pivot_graph maxcut_anchor_three_initial_coloring
Source
The existing optimal initial profile cuts the added edge.
Verified
10 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8
  • maxcut_anchor_neutral_pivot_graphThe known 91-vertex anchor graph with one extra edge from the first core vertex to a previously nonadjacent anchor of its displayed target…
  • maxcut_anchor_three_initial_optimalThe displayed initial coloring sigma of the 91-vertex graph G_3 in arXiv:2610.04948 maximizes social welfare among all three-colorings.
  • is_maxcut_optimalA coloring σ is optimal if no coloring τ : V → [k] has larger social welfare (equivalently, σ is a maximum k-cut).
  • 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)…
  • maxcut_anchor_three_graphThe 91-vertex graph G_3 of arXiv:2610.04948: a 16-vertex core A,B,C,D and three anchor classes of 25 vertices. Indices and colors are…
  • maxcut_utility_eq_sumThe Max-k-Cut utility of v is the sum over all w of the indicator that w is a neighbour of v with a different color.
  • maxcut_anchor_three_initial_coloringThe initial coloring sigma of the paper graph G_3: A and D have color 0, B color 1, C color 2, and anchor class j has color j.
  • maxcut_welfareThe social welfare of a coloring σ in the Max-k-Cut game: the sum over all players v of u_v(σ), equal to twice the cut value.

Lean source view module on GitHub

instance : DecidableRel maxcut_anchor_neutral_pivot_graph.Adj := by
  unfold maxcut_anchor_neutral_pivot_graph maxcut_anchor_three_graph
  infer_instance

lemma maxcut_anchor_neutral_pivot_initial_optimal_welfare_add_two
    {V : Type} [Fintype V] [DecidableEq V] {G H : SimpleGraph V}
    [DecidableRel G.Adj] [DecidableRel H.Adj] {k : ℕ} (σ : V → Fin k) (x y : V)
    (hH : ∀ u v, H.Adj u v → G.Adj u v ∨ (u = x ∧ v = y) ∨ (u = y ∧ v = x)) :
    maxcut_welfare H σ ≤ maxcut_welfare G σ + 2 := by
  rw [maxcut_welfare, maxcut_welfare]
  have hterm : ∀ v : V, maxcut_utility H σ v ≤
      maxcut_utility G σ v + (if v = x then 1 else 0) + (if v = y then 1 else 0) := by
    intro v
    rw [maxcut_utility_eq_sum, maxcut_utility_eq_sum]
    have h1 : (∑ w, (if v = x ∧ w = y then 1 else 0 : ℕ)) = (if v = x then 1 else 0) := by
      by_cases hv : v = x
      · simp only [hv, if_true, true_and, Finset.sum_ite_eq']
        simp
      · simp [hv]
    have h2 : (∑ w, (if v = y ∧ w = x then 1 else 0 : ℕ)) = (if v = y then 1 else 0) := by
      by_cases hv : v = y
      · simp only [hv, if_true, true_and, Finset.sum_ite_eq']
        simp
      · simp [hv]
    calc ∑ w, (if H.Adj v w ∧ σ w ≠ σ v then 1 else 0)
        ≤ ∑ w, ((if G.Adj v w ∧ σ w ≠ σ v then 1 else 0) + (if v = x ∧ w = y then 1 else 0) + (if v = y ∧ w = x then 1 else 0)) := by
          apply Finset.sum_le_sum
          intro w _
          by_cases h : H.Adj v w ∧ σ w ≠ σ v
          · rw [if_pos h]
            rcases hH v w h.1 with hg | ⟨hr1, hr2⟩ | ⟨hr1, hr2⟩
            · rw [if_pos ⟨hg, h.2⟩]; omega
            · rw [if_pos (show v = x ∧ w = y from ⟨hr1, hr2⟩)]; omega
            · rw [if_pos (show v = y ∧ w = x from ⟨hr1, hr2⟩)]; omega
          · rw [if_neg h]; exact Nat.zero_le _
      _ = (∑ w, (if G.Adj v w ∧ σ w ≠ σ v then 1 else 0)) + (if v = x then 1 else 0) + (if v = y then 1 else 0) := by
          rw [Finset.sum_add_distrib, Finset.sum_add_distrib, h1, h2]
  calc ∑ v, maxcut_utility H σ v
      ≤ ∑ v, (maxcut_utility G σ v + (if v = x then 1 else 0) + (if v = y then 1 else 0)) :=
        Finset.sum_le_sum fun v _ => hterm v
    _ = ∑ v, maxcut_utility G σ v + 2 := by
        rw [Finset.sum_add_distrib, Finset.sum_add_distrib]
        have hx : (∑ v : V, if v = x then (1:ℕ) else 0) = 1 := by
          rw [Finset.sum_ite_eq']; simp
        have hy : (∑ v : V, if v = y then (1:ℕ) else 0) = 1 := by
          rw [Finset.sum_ite_eq']; simp
        rw [hx, hy]

lemma maxcut_anchor_neutral_pivot_initial_optimal_welfare_add_two_le
    {V : Type} [Fintype V] [DecidableEq V] {G H : SimpleGraph V}
    [DecidableRel G.Adj] [DecidableRel H.Adj] {k : ℕ} (σ : V → Fin k) (x y : V)
    (hH : ∀ u v, H.Adj u v ↔ G.Adj u v ∨ (u = x ∧ v = y) ∨ (u = y ∧ v = x))
    (hnew : ¬ G.Adj x y) (hcolor : σ x ≠ σ y) :
    maxcut_welfare G σ + 2 ≤ maxcut_welfare H σ := by
  have hxy : x ≠ y := fun h => hcolor (by rw [h])
  rw [maxcut_welfare, maxcut_welfare]
  have hterm : ∀ v : V, maxcut_utility G σ v + (if v = x then 1 else 0) + (if v = y then 1 else 0) ≤ maxcut_utility H σ v := by
    intro v
    rw [maxcut_utility, maxcut_utility]
    by_cases hvx : v = x
    · subst v
      have hsub : insert y (Finset.univ.filter fun w => G.Adj x w ∧ σ w ≠ σ x) ⊆
          (Finset.univ.filter fun w => H.Adj x w ∧ σ w ≠ σ x) := by
        rw [Finset.insert_subset_iff]
        refine ⟨?_, ?_⟩
        · simp only [Finset.mem_filter, Finset.mem_univ, true_and]
          exact ⟨(hH x y).mpr (Or.inr (Or.inl ⟨rfl, rfl⟩)), hcolor.symm⟩
        · intro w hw
          simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hw ⊢
          exact ⟨(hH x w).mpr (Or.inl hw.1), hw.2⟩
      have hnot : y ∉ (Finset.univ.filter fun w => G.Adj x w ∧ σ w ≠ σ x) := by
        simp only [Finset.mem_filter, Finset.mem_univ, true_and]
        exact fun h => hnew h.1
      have hcard := Finset.card_le_card hsub
      rw [Finset.card_insert_of_notMem hnot] at hcard
      rw [if_pos rfl, if_neg hxy]
      simpa using hcard
    · by_cases hvy : v = y
      · subst v
        have hsub : insert x (Finset.univ.filter fun w => G.Adj y w ∧ σ w ≠ σ y) ⊆
            (Finset.univ.filter fun w => H.Adj y w ∧ σ w ≠ σ y) := by
          rw [Finset.insert_subset_iff]
          refine ⟨?_, ?_⟩
          · simp only [Finset.mem_filter, Finset.mem_univ, true_and]
            exact ⟨(hH y x).mpr (Or.inr (Or.inr ⟨rfl, rfl⟩)), hcolor⟩
          · intro w hw
            simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hw ⊢
            exact ⟨(hH y w).mpr (Or.inl hw.1), hw.2⟩
        have hnot : x ∉ (Finset.univ.filter fun w => G.Adj y w ∧ σ w ≠ σ y) := by
          simp only [Finset.mem_filter, Finset.mem_univ, true_and]
          exact fun h => hnew h.1.symm
        have hcard := Finset.card_le_card hsub
        rw [Finset.card_insert_of_notMem hnot] at hcard
        rw [if_neg hvx, if_pos rfl]
        simpa using hcard
      · have hsub : (Finset.univ.filter fun w => G.Adj v w ∧ σ w ≠ σ v) ⊆
            (Finset.univ.filter fun w => H.Adj v w ∧ σ w ≠ σ v) := by
          intro w hw
          simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hw ⊢
          exact ⟨(hH v w).mpr (Or.inl hw.1), hw.2⟩
        have hcard := Finset.card_le_card hsub
        rw [if_neg hvx, if_neg hvy]
        simpa using hcard
  have hsum : ∑ v, (maxcut_utility G σ v + (if v = x then 1 else 0) + (if v = y then 1 else 0))
      = ∑ v, maxcut_utility G σ v + 2 := by
    rw [Finset.sum_add_distrib, Finset.sum_add_distrib]
    have hx : (∑ v : V, if v = x then (1:ℕ) else 0) = 1 := by
      rw [Finset.sum_ite_eq']; simp
    have hy : (∑ v : V, if v = y then (1:ℕ) else 0) = 1 := by
      rw [Finset.sum_ite_eq']; simp
    rw [hx, hy]
  calc ∑ v, maxcut_utility G σ v + 2
      = ∑ v, (maxcut_utility G σ v + (if v = x then 1 else 0) + (if v = y then 1 else 0)) := hsum.symm
    _ ≤ ∑ v, maxcut_utility H σ v := Finset.sum_le_sum fun v _ => hterm v

theorem maxcut_anchor_neutral_pivot_initial_optimal : is_maxcut_optimal maxcut_anchor_neutral_pivot_graph maxcut_anchor_three_initial_coloring := by
  intro τ
  letI : DecidableRel maxcut_anchor_three_graph.Adj := by unfold maxcut_anchor_three_graph; infer_instance
  have hAdj : ∀ u v : Fin 16 ⊕ (Fin 3 × Fin 25),
      maxcut_anchor_neutral_pivot_graph.Adj u v ↔
        maxcut_anchor_three_graph.Adj u v ∨
          (u = Sum.inl 0 ∧ v = Sum.inr ((2:Fin 3), (24:Fin 25))) ∨
          (u = Sum.inr ((2:Fin 3), (24:Fin 25)) ∧ v = Sum.inl 0) := by
    intro u v
    unfold maxcut_anchor_neutral_pivot_graph
    rw [SimpleGraph.fromRel_adj]
    constructor
    · rintro ⟨-, (h | ⟨e1, e2⟩) | (h | ⟨e1, e2⟩)⟩
      · exact Or.inl h
      · exact Or.inr (Or.inl ⟨e1, e2⟩)
      · exact Or.inl h.symm
      · exact Or.inr (Or.inr ⟨e2, e1⟩)
    · rintro (h | ⟨e1, e2⟩ | ⟨e1, e2⟩)
      · exact ⟨maxcut_anchor_three_graph.ne_of_adj h, Or.inl (Or.inl h)⟩
      · subst u; subst v
        refine ⟨?_, ?_⟩
        · simp
        · exact Or.inl (Or.inr ⟨rfl, rfl⟩)
      · subst u; subst v
        refine ⟨?_, ?_⟩
        · simp
        · exact Or.inr (Or.inr ⟨rfl, rfl⟩)
  have hnew : ¬ maxcut_anchor_three_graph.Adj (Sum.inl 0) (Sum.inr ((2:Fin 3), (24:Fin 25))) := by
    decide
  have hcolor : maxcut_anchor_three_initial_coloring (Sum.inl 0) ≠
      maxcut_anchor_three_initial_coloring (Sum.inr ((2:Fin 3), (24:Fin 25))) := by
    decide
  have hupper : maxcut_welfare maxcut_anchor_neutral_pivot_graph τ ≤
      maxcut_welfare maxcut_anchor_three_graph τ + 2 :=
    maxcut_anchor_neutral_pivot_initial_optimal_welfare_add_two τ
      (Sum.inl 0) (Sum.inr ((2:Fin 3), (24:Fin 25)))
      (fun u v h => (hAdj u v).1 h)
  have hlower : maxcut_welfare maxcut_anchor_three_graph maxcut_anchor_three_initial_coloring + 2 ≤
      maxcut_welfare maxcut_anchor_neutral_pivot_graph maxcut_anchor_three_initial_coloring :=
    maxcut_anchor_neutral_pivot_initial_optimal_welfare_add_two_le
      maxcut_anchor_three_initial_coloring (Sum.inl 0) (Sum.inr ((2:Fin 3), (24:Fin 25)))
      hAdj hnew hcolor
  have hopt := maxcut_anchor_three_initial_optimal τ
  calc maxcut_welfare maxcut_anchor_neutral_pivot_graph τ
      ≤ maxcut_welfare maxcut_anchor_three_graph τ + 2 := hupper
    _ ≤ maxcut_welfare maxcut_anchor_three_graph maxcut_anchor_three_initial_coloring + 2 := by omega
    _ ≤ maxcut_welfare maxcut_anchor_neutral_pivot_graph maxcut_anchor_three_initial_coloring := hlower
See it in the graphDiscuss this resultChallenge it