AFTD Auto-Formalizing Theoretical Domains

maxcut_pinned_twins_optimum_rigidity

theoremverified

Every welfare-maximizing 3-coloring ρ of the 182-vertex pinned twins graph maxcut_pinned_twins_graph is, up to one global permutation p of the three colors, the doubled initial coloring: ρ = fun v => p (maxcut_anchor_three_initial_coloring v.1).

Statement

theorem maxcut_pinned_twins_optimum_rigidity :
    ∀ ρ : ((Fin 16 ⊕ (Fin 3 × Fin 25)) × Fin 2) → Fin 3,
      is_maxcut_optimal maxcut_pinned_twins_graph ρ →
      ∃ p : Equiv.Perm (Fin 3),
        ρ = fun v => p (maxcut_anchor_three_initial_coloring v.1)
Source
Rigidity premise of maxcut_pinned_twins_refutes_of_rigidity, towards OP-89 (arXiv:2610.04948, Section 4, Question 2).
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • maxcut_pinned_twins_graphA candidate counterexample graph on 182 vertices. Replace each vertex of the paper graph G_3 by two independent twins, replace each old…
  • 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_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_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_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.
  • maxcut_utility_add_monochromatic_cardA player's utility plus the number of its neighbours sharing its colour equals its degree.
Used by 2

The proof, explained

Maximizing Max-Cut welfare is equivalent to minimizing monochromatic edges, as welfare and monochromatic edge count sum to the degree sum. For the 182-vertex pinned twins graph, an averaging identity shows that four times the average monochromatic count over all 2^91 twin slices equals the monochromatic count on doubled base edges. Because the doubled initial coloring achieves 192 monochromatic pairs (four times the minimum 48 on the anchor graph G₃) and contains no monochromatic pinning edges, any optimal coloring must achieve equality: every slice has count 48 on G₃ and no pinning edge is monochromatic. Anchor rigidity then forces all anchor twins to follow a single color permutation p, and the absence of monochromatic pinning edges uniquely forces all core twins to match p applied to their initial color.

  1. Adjacency in the anchor-3 graph G₃ lifts to adjacency between all twin copies in the pinned twins graph.

    The edge relation of the pinned twins graph includes all pairs whose first components are adjacent in G₃, forming K_{2,2} connections between twins. Since adjacent vertices in G₃ are distinct, their twin copies are distinct.

    lines 12–21

    uses SimpleGraph.fromRel_adj

    private instance maxcut_pinned_twins_optimum_rigidity_base_dec : DecidableRel maxcut_anchor_three_graph.Adj := by
      unfold maxcut_anchor_three_graph; infer_instance
    private instance maxcut_pinned_twins_optimum_rigidity_pinned_dec : DecidableRel maxcut_pinned_twins_graph.Adj := by
      unfold maxcut_pinned_twins_graph; infer_instance
    
    private lemma lift_adj (a b : PW) (h : maxcut_anchor_three_graph.Adj a.1 b.1) :
        maxcut_pinned_twins_graph.Adj a b := by
      simp only [maxcut_pinned_twins_graph, SimpleGraph.fromRel_adj]
      exact ⟨fun hab => h.ne (congrArg Prod.fst hab), Or.inl (Or.inl h)⟩
    
  2. Pinning edges connect core vertices to anchor vertices with different initial colors, and are disjoint from base edges. automation

    By definition, pinning edges connect core vertices u to anchor vertices (j, 24) of twin copy 0 for each color j ≠ initial(u). An exhaustive decision procedure (`decide`) verifies that all such pinning edges exist in the pinned twins graph and do not originate from G₃ base edges.

    lines 22–50

    private def pin (a b : PW) : Prop :=
      match a.1, b.1 with
      | .inl i, .inr (j, x) => x.val = 24 ∧ b.2.val = 0 ∧
          j ≠ maxcut_anchor_three_initial_coloring (.inl i)
      | _, _ => False
    
    private lemma adj_iff (a b : PW) : maxcut_pinned_twins_graph.Adj a b ↔
        a ≠ b ∧ ((maxcut_anchor_three_graph.Adj a.1 b.1 ∨ pin a b) ∨
          (maxcut_anchor_three_graph.Adj b.1 a.1 ∨ pin b a)) := Iff.rfl
    
    private lemma pin_ne (a b : PW) (h : pin a b) :
        maxcut_anchor_three_initial_coloring b.1 ≠ maxcut_anchor_three_initial_coloring a.1 := by
      rcases a with ⟨a1, a2⟩
      rcases b with ⟨b1, b2⟩
      cases a1 with
      | inl i =>
        cases b1 with
        | inl i' => exact h.elim
        | inr jx =>
          obtain ⟨j, x⟩ := jx
          exact h.2.2
      | inr jx => exact h.elim
    
    private lemma pin_adj : ∀ (u : Fin 16) (s : Fin 2) (j : Fin 3),
        j ≠ maxcut_anchor_three_initial_coloring (.inl u) →
        maxcut_pinned_twins_graph.Adj (.inl u, s) (.inr (j, 24), 0) ∧
        ¬ maxcut_anchor_three_graph.Adj (.inl u) (.inr (j, 24)) := by
      decide
    
  3. Maximizing Max-Cut welfare is equivalent to minimizing the monochromatic directed edge count. automation

    At every vertex v, the cut utility plus the monochromatic degree equals the vertex degree (by `maxcut_utility_add_monochromatic_card`). Summing over all vertices shows that welfare plus `mono` equals the fixed degree sum `∑ v, degree v`. Therefore, any welfare-maximizing coloring minimizes `mono`. Linear arithmetic (`omega`) closes the inequality.

    lines 51–69

    uses maxcut_utility_add_monochromatic_card, welfare_add_mono

    private def mono {X : Type} [Fintype X] (H : SimpleGraph X) [DecidableRel H.Adj] (ρ : X → Fin 3) : ℕ :=
      ∑ v, (Finset.univ.filter fun w => H.Adj v w ∧ ρ w = ρ v).card
    
    private lemma mono_sum {X : Type} [Fintype X] (H : SimpleGraph X) [DecidableRel H.Adj] (ρ : X → Fin 3) :
        mono H ρ = ∑ v, ∑ w, if H.Adj v w ∧ ρ w = ρ v then 1 else 0 := by
      simp only [mono, Finset.card_filter]
    
    private lemma welfare_add_mono {X : Type} [Fintype X] (H : SimpleGraph X) [DecidableRel H.Adj]
        (ρ : X → Fin 3) : maxcut_welfare H ρ + mono H ρ = ∑ v, H.degree v := by
      rw [maxcut_welfare, mono, ← Finset.sum_add_distrib]
      exact Finset.sum_congr rfl fun v _ => maxcut_utility_add_monochromatic_card H ρ v
    
    private lemma mono_le_of_optimal {X : Type} [Fintype X] (H : SimpleGraph X) [DecidableRel H.Adj]
        (ρ τ : X → Fin 3) (h : is_maxcut_optimal H ρ) : mono H ρ ≤ mono H τ := by
      have h1 := h τ
      have h2 := welfare_add_mono H ρ
      have h3 := welfare_add_mono H τ
      omega
    
  4. For any independent set S, twice the sum of monochromatic degrees of vertices in S is at most the total monochromatic count.

    Because S contains no edges, the double sum of monochromatic edge indicators within S is zero. Decomposing the full double sum over the universe into pairs in S × Sᶜ, Sᶜ × S, and Sᶜ × Sᶜ shows that the cross-terms contribute twice the monochromatic degrees of S, bounded by the total sum.

    lines 70–106

    uses Finset.sum_add_sum_compl, mono_sum

    private lemma independent_mono_bound {X : Type} [Fintype X] [DecidableEq X]
        (H : SimpleGraph X) [DecidableRel H.Adj] (ρ : X → Fin 3)
        (S : Finset X) (hind : ∀ v ∈ S, ∀ w ∈ S, ¬ H.Adj v w) :
        2 * (∑ v ∈ S, (Finset.univ.filter fun w => H.Adj v w ∧ ρ w = ρ v).card)
          ≤ mono H ρ := by
      classical
      let f : X → X → ℕ := fun v w => if H.Adj v w ∧ ρ w = ρ v then 1 else 0
      have hsym (v w : X) : f v w = f w v := by
        dsimp [f]
        congr 1
        exact propext ⟨fun h => ⟨h.1.symm, h.2.symm⟩, fun h => ⟨h.1.symm, h.2.symm⟩⟩
      have hzero : ∑ v ∈ S, ∑ w ∈ S, f v w = 0 := by
        apply Finset.sum_eq_zero
        intro v hv
        apply Finset.sum_eq_zero
        intro w hw
        simp [f, hind v hv w hw]
      have hcross : ∑ v ∈ Sᶜ, ∑ w ∈ S, f v w = ∑ v ∈ S, ∑ w ∈ Sᶜ, f v w := by
        rw [Finset.sum_comm]
        exact Finset.sum_congr rfl fun v _ => Finset.sum_congr rfl fun w _ => hsym w v
      have hsplit (v : X) : ∑ w, f v w = ∑ w ∈ S, f v w + ∑ w ∈ Sᶜ, f v w :=
        (Finset.sum_add_sum_compl S _).symm
      have hall : mono H ρ =
          2 * (∑ v ∈ S, ∑ w ∈ Sᶜ, f v w) + ∑ v ∈ Sᶜ, ∑ w ∈ Sᶜ, f v w := by
        rw [mono_sum]
        change (∑ v, ∑ w, f v w) = _
        rw [← Finset.sum_add_sum_compl S]
        simp only [hsplit, Finset.sum_add_distrib, hzero, hcross]
        omega
      have hpart : (∑ v ∈ S, (Finset.univ.filter fun w => H.Adj v w ∧ ρ w = ρ v).card) =
          ∑ v ∈ S, ∑ w ∈ Sᶜ, f v w := by
        simp only [Finset.card_filter]
        change (∑ v ∈ S, ∑ w, f v w) = _
        simp only [hsplit, Finset.sum_add_distrib, hzero, zero_add]
      rw [hpart, hall]
      omega
    
  5. If an independent set S satisfies mono H ρ < 2 * |S|, it contains a vertex with no incident monochromatic edges.

    If every vertex in S had at least one incident monochromatic edge, their sum of monochromatic degrees would be at least |S|. The independent set bound would then force mono H ρ ≥ 2 * |S|, a contradiction.

    lines 107–123

    uses independent_mono_bound

    private lemma exists_good_of_independent {X : Type} [Fintype X] [DecidableEq X]
        (H : SimpleGraph X) [DecidableRel H.Adj] (ρ : X → Fin 3)
        (S : Finset X) (hind : ∀ v ∈ S, ∀ w ∈ S, ¬ H.Adj v w)
        (hsmall : mono H ρ < 2 * S.card) :
        ∃ v ∈ S, ∀ w, H.Adj v w → ρ w ≠ ρ v := by
      classical
      by_contra h
      push Not at h
      have hpos : ∀ v ∈ S, 1 ≤ (Finset.univ.filter fun w => H.Adj v w ∧ ρ w = ρ v).card := by
        intro v hv
        obtain ⟨w, hadj, hc⟩ := h v hv
        exact Finset.card_pos.mpr ⟨w, by simp [hadj, hc]⟩
      have hsum := Finset.sum_le_sum hpos
      have hb := independent_mono_bound H ρ S hind
      simp only [Finset.sum_const, smul_eq_mul, mul_one] at hsum
      omega
    
  6. Anchor vertices form a complete tripartite graph, and every 3-coloring of G₃ has at least 48 monochromatic directed edges. automation

    Anchor vertices (j, i) are adjacent iff j ≠ l, partitioning into three independent sets of 25 vertices to form K_{25,25,25}. The initial coloring has exactly 48 monochromatic pairs by `decide`, and because this initial coloring is Max-Cut optimal on G₃ (`maxcut_anchor_three_initial_optimal`), every coloring of G₃ has mono ≥ 48.

    lines 124–145

    uses mono_sigma, maxcut_anchor_three_initial_optimal, mono_le_of_optimal

    private lemma anchor_adj (j l : Fin 3) (i t : Fin 25) :
        maxcut_anchor_three_graph.Adj (.inr (j,i)) (.inr (l,t)) ↔ j ≠ l := by
      change ((Sum.inr (j,i) : PV) ≠ Sum.inr (l,t) ∧ (j ≠ l ∨ l ≠ j)) ↔ j ≠ l
      constructor
      · rintro ⟨_, h | h⟩
        · exact h
        · exact h.symm
      · intro h
        refine ⟨?_, Or.inl h⟩
        intro heq
        exact h (congrArg Prod.fst (Sum.inr.inj heq))
    
    private lemma mono_sigma :
        mono maxcut_anchor_three_graph maxcut_anchor_three_initial_coloring = 48 := by
      decide
    
    private lemma mono_G_ge (ρ : PV → Fin 3) : 48 ≤ mono maxcut_anchor_three_graph ρ := by
      have h := mono_le_of_optimal maxcut_anchor_three_graph maxcut_anchor_three_initial_coloring ρ
        maxcut_anchor_three_initial_optimal
      rw [mono_sigma] at h
      exact h
    
  7. Any coloring of G₃ with mono < 50 assigns a constant color to each anchor class via a global permutation of the colors.

    Each color class S_j of 25 anchor vertices is independent. Since mono < 50 = 2 * 25, each S_j contains a good vertex with monochromatic degree 0. Since good vertices in different classes are adjacent, their colors are distinct, defining a color permutation p. Every other vertex in S_j must also receive color p(j), for otherwise it would form a monochromatic edge with the good vertex of that color class.

    lines 146–180

    uses anchor_adj, exists_good_of_independent

    private lemma anchor_rigidity (ρ : PV → Fin 3) (hsmall : mono maxcut_anchor_three_graph ρ < 50) :
        ∃ p : Equiv.Perm (Fin 3), ∀ j i, ρ (.inr (j,i)) = p j := by
      classical
      have hgood : ∀ j : Fin 3, ∃ i : Fin 25,
          ∀ w, maxcut_anchor_three_graph.Adj (.inr (j,i)) w → ρ w ≠ ρ (.inr (j,i)) := by
        intro j
        let S : Finset PV := Finset.univ.image fun i : Fin 25 => Sum.inr (j,i)
        have hcard : S.card = 25 := by
          rw [Finset.card_image_of_injective _ (by intro a b h; simpa using h)]
          decide
        have hind : ∀ v ∈ S, ∀ w ∈ S, ¬ maxcut_anchor_three_graph.Adj v w := by
          intro v hv w hw
          obtain ⟨i, _, rfl⟩ := Finset.mem_image.mp hv
          obtain ⟨t, _, rfl⟩ := Finset.mem_image.mp hw
          simp [anchor_adj]
        obtain ⟨v, hv, hg⟩ := exists_good_of_independent maxcut_anchor_three_graph ρ S hind
          (by omega)
        obtain ⟨i, _, rfl⟩ := Finset.mem_image.mp hv
        exact ⟨i, hg⟩
      choose gi hg using hgood
      let c : Fin 3 → Fin 3 := fun j => ρ (.inr (j, gi j))
      have hi : Function.Injective c := by
        intro j l heq
        by_contra hne
        exact hg j (.inr (l, gi l)) ((anchor_adj j l _ _).2 hne) heq.symm
      have hb : Function.Bijective c := (Fintype.bijective_iff_injective_and_card c).2 ⟨hi, rfl⟩
      refine ⟨Equiv.ofBijective c hb, ?_⟩
      intro j i
      obtain ⟨l, hl⟩ := hb.2 (ρ (.inr (j,i)))
      have heq : l = j := by
        by_contra hne
        exact hg l (.inr (j,i)) ((anchor_adj l j _ _).2 hne) hl.symm
      subst l
      exact hl.symm
    
  8. The base edge monochromatic count is at most the total monochromatic count, and strictly less if any pinning edge is monochromatic.

    Every base edge of G₃ gives rise to edges in the pinned twins graph, so twinBase ≤ mono. If any pinning edge is monochromatic, it contributes to mono but not to twinBase, making the inequality strict.

    lines 181–217

    uses mono_sum, lift_adj, pin_adj, ind_le

    /-- Monochromatic ordered pairs of the twin graph that come from edges of `G_3`. -/
    private def twinBase (ρ : PW → Fin 3) : ℕ :=
      ∑ a : PW, ∑ b : PW, if maxcut_anchor_three_graph.Adj a.1 b.1 ∧ ρ b = ρ a then 1 else 0
    
    private lemma base_split (ρ : PW → Fin 3) : twinBase ρ = ∑ v : PV, ∑ w : PV, ∑ s : Fin 2, ∑ t : Fin 2,
        if maxcut_anchor_three_graph.Adj v w ∧ ρ (w, t) = ρ (v, s) then 1 else 0 := by
      unfold twinBase
      simp only [Fintype.sum_prod_type]
      exact Finset.sum_congr rfl fun v _ => Finset.sum_comm
    
    private lemma ind_le (ρ : PW → Fin 3) (a b : PW) :
        (if maxcut_anchor_three_graph.Adj a.1 b.1 ∧ ρ b = ρ a then 1 else 0) ≤
          (if maxcut_pinned_twins_graph.Adj a b ∧ ρ b = ρ a then 1 else 0) := by
      by_cases h : maxcut_anchor_three_graph.Adj a.1 b.1 ∧ ρ b = ρ a
      · rw [if_pos h, if_pos ⟨lift_adj a b h.1, h.2⟩]
      · rw [if_neg h]
        exact Nat.zero_le _
    
    private lemma base_le_mono (ρ : PW → Fin 3) : twinBase ρ ≤ mono maxcut_pinned_twins_graph ρ := by
      rw [mono_sum]
      exact Finset.sum_le_sum fun a _ => Finset.sum_le_sum fun b _ => ind_le ρ a b
    
    private lemma base_lt_mono (ρ : PW → Fin 3) (u : Fin 16) (s : Fin 2) (j : Fin 3)
        (hj : j ≠ maxcut_anchor_three_initial_coloring (.inl u))
        (heq : ρ (.inr (j, 24), 0) = ρ (.inl u, s)) :
        twinBase ρ < mono maxcut_pinned_twins_graph ρ := by
      rw [mono_sum]
      apply Finset.sum_lt_sum
      · exact fun a _ => Finset.sum_le_sum fun b _ => ind_le ρ a b
      · refine ⟨(.inl u, s), Finset.mem_univ _, ?_⟩
        apply Finset.sum_lt_sum
        · exact fun b _ => ind_le ρ _ b
        · refine ⟨(.inr (j, 24), 0), Finset.mem_univ _, ?_⟩
          obtain ⟨hadj, hnot⟩ := pin_adj u s j hj
          rw [if_neg (fun h => hnot h.1), if_pos ⟨hadj, heq⟩]
          exact Nat.zero_lt_one
    
  9. The doubled initial coloring on the pinned twins graph has monochromatic count exactly 192.

    In the doubled initial coloring, no pinning edges are monochromatic because pinning edges connect vertices of differing initial colors (`pin_ne`). All monochromatic pairs come from the doubled base edges of G₃, each contributing 2 * 2 = 4 pairs per monochromatic base pair. Since the initial coloring on G₃ has 48 monochromatic pairs, the doubled coloring has 4 * 48 = 192.

    lines 218–252

    uses adj_iff, pin_ne, lift_adj, mono_sum, base_split, mono_sigma

    private lemma mono_sigma' :
        mono maxcut_pinned_twins_graph (fun v => maxcut_anchor_three_initial_coloring v.1) = 192 := by
      have hpt : ∀ a b : PW,
          (if maxcut_pinned_twins_graph.Adj a b ∧ maxcut_anchor_three_initial_coloring b.1 =
              maxcut_anchor_three_initial_coloring a.1 then 1 else 0) =
          (if maxcut_anchor_three_graph.Adj a.1 b.1 ∧ maxcut_anchor_three_initial_coloring b.1 =
              maxcut_anchor_three_initial_coloring a.1 then 1 else 0) := by
        intro a b
        congr 1
        apply propext
        constructor
        · rintro ⟨hadj, hc⟩
          refine ⟨?_, hc⟩
          rcases (adj_iff a b).1 hadj with ⟨_, (h | h) | (h | h)⟩
          · exact h
          · exact absurd hc (pin_ne a b h)
          · exact h.symm
          · exact absurd hc.symm (pin_ne b a h)
        · rintro ⟨hadj, hc⟩
          exact ⟨lift_adj a b hadj, hc⟩
      rw [mono_sum]
      simp only [hpt]
      change twinBase (fun v => maxcut_anchor_three_initial_coloring v.1) = 192
      rw [base_split]
      have h48 := mono_sigma
      rw [mono_sum] at h48
      rw [show (192 : ℕ) = 4 * 48 from rfl, ← h48, Finset.mul_sum]
      apply Finset.sum_congr rfl
      intro v _
      rw [Finset.mul_sum]
      apply Finset.sum_congr rfl
      intro w _
      simp only [Fin.sum_univ_two]
      ring
    
  10. Averaging any function of two distinct vertices over all twin slices distributes uniformly over the four twin assignments. automation

    For distinct vertices v ≠ w, translations c ↦ c + a 1_v + b 1_w act as an involutive permutation on the space of slices {0, 1}^|X|. By permutation invariance of sums, the sum of F(c(v) + a, c(w) + b) is invariant under (a, b). Summing over the four choices of (a, b) yields 4 ∑_c F(c(v), c(w)) = 2^|X| ∑_{s,t} F(s, t). Finite arithmetic over Fin 2 is verified by `decide` and algebraic rearrangement by `ring`.

    lines 253–300

    private def slice (ρ : PW → Fin 3) (c : PV → Fin 2) : PV → Fin 3 := fun v => ρ (v, c v)
    
    private lemma pair_avg {X : Type} [Fintype X] [DecidableEq X] (v w : X) (hvw : v ≠ w)
        (Fv : Fin 2 → Fin 2 → ℕ) :
        4 * ∑ c : X → Fin 2, Fv (c v) (c w) = Fintype.card (X → Fin 2) * ∑ s, ∑ t, Fv s t := by
      have hz : ∀ z a : Fin 2, z + a + a = z := by decide
      have key : ∀ a b : Fin 2, ∑ c : X → Fin 2, Fv (c v + a) (c w + b) =
          ∑ c : X → Fin 2, Fv (c v) (c w) := by
        intro a b
        let e : (X → Fin 2) → (X → Fin 2) := fun c x =>
          if x = v then c x + a else if x = w then c x + b else c x
        have he : Function.Involutive e := by
          intro c
          funext x
          simp only [e]
          by_cases h1 : x = v
          · simp [h1, hz]
          · by_cases h2 : x = w
            · simp [h2, Ne.symm hvw, hz]
            · simp [h1, h2]
        have hev : ∀ c, e c v = c v + a := by intro c; simp [e]
        have hew : ∀ c, e c w = c w + b := by intro c; simp [e, Ne.symm hvw]
        calc ∑ c : X → Fin 2, Fv (c v + a) (c w + b)
            = ∑ c : X → Fin 2, (fun d : X → Fin 2 => Fv (d v) (d w))
                (Function.Involutive.toPerm e he c) := by
              apply Finset.sum_congr rfl
              intro c _
              simp only [Function.Involutive.coe_toPerm, hev, hew]
          _ = ∑ c : X → Fin 2, Fv (c v) (c w) := Equiv.sum_comp (Function.Involutive.toPerm e he) (fun d : X → Fin 2 => Fv (d v) (d w))
      have hinner : ∀ c : X → Fin 2, ∑ a : Fin 2, ∑ b : Fin 2, Fv (c v + a) (c w + b) =
          ∑ s, ∑ t, Fv s t := by
        intro c
        have h1 := Equiv.sum_comp (Equiv.addLeft (c v)) (fun s => ∑ t, Fv s t)
        rw [← h1]
        apply Finset.sum_congr rfl
        intro a _
        exact (Equiv.sum_comp (Equiv.addLeft (c w)) (fun t => Fv (c v + a) t))
      calc 4 * ∑ c : X → Fin 2, Fv (c v) (c w)
          = ∑ a : Fin 2, ∑ b : Fin 2, ∑ c : X → Fin 2, Fv (c v + a) (c w + b) := by
            simp only [key, Finset.sum_const, Finset.card_univ, Fintype.card_fin, smul_eq_mul]
            ring
        _ = ∑ a : Fin 2, ∑ c : X → Fin 2, ∑ b : Fin 2, Fv (c v + a) (c w + b) :=
            Finset.sum_congr rfl (fun a _ => Finset.sum_comm)
        _ = ∑ c : X → Fin 2, ∑ a : Fin 2, ∑ b : Fin 2, Fv (c v + a) (c w + b) := Finset.sum_comm
        _ = ∑ c : X → Fin 2, ∑ s, ∑ t, Fv s t := Finset.sum_congr rfl (fun c _ => hinner c)
        _ = Fintype.card (X → Fin 2) * ∑ s, ∑ t, Fv s t := by
            simp only [Finset.sum_const, Finset.card_univ, smul_eq_mul]
    
  11. Four times the sum of slice monochromatic counts equals 2^|PV| times the twin base monochromatic count.

    By swapping the order of summation, non-edges contribute zero, while for each base edge v ~ w, `pair_avg` converts the sum over all slices into 2^|PV| / 4 times the sum over the four twin copies, yielding the exact identity.

    lines 301–321

    uses mono_sum, base_split, pair_avg

    private lemma avg (ρ : PW → Fin 3) :
        4 * ∑ c : PV → Fin 2, mono maxcut_anchor_three_graph (slice ρ c) =
          Fintype.card (PV → Fin 2) * twinBase ρ := by
      simp only [mono_sum, slice]
      rw [base_split]
      have hswap : ∀ I : (PV → Fin 2) → PV → PV → ℕ,
          ∑ c, ∑ v, ∑ w, I c v w = ∑ v, ∑ w, ∑ c, I c v w := by
        intro I
        rw [Finset.sum_comm]
        exact Finset.sum_congr rfl fun v _ => Finset.sum_comm
      rw [hswap, Finset.mul_sum, Finset.mul_sum]
      apply Finset.sum_congr rfl
      intro v _
      rw [Finset.mul_sum, Finset.mul_sum]
      apply Finset.sum_congr rfl
      intro w _
      by_cases hvw : maxcut_anchor_three_graph.Adj v w
      · simp only [hvw, true_and]
        exact pair_avg v w hvw.ne (fun s t => if ρ (w, t) = ρ (v, s) then 1 else 0)
      · simp [hvw]
    
  12. For an optimal coloring ρ, twinBase = 192, mono = 192, every slice achieves mono = 48 on G₃, and no pinning edge is monochromatic.

    Optimality implies mono ≤ 192, so twinBase ≤ 192. Conversely, every slice has mono ≥ 48 on G₃, so averaging yields 4 * (2^|PV| * 48) ≤ 2^|PV| * twinBase, forcing twinBase ≥ 192. Hence twinBase = mono = 192, every slice achieves the minimal count 48, and no pinning edge can be monochromatic (which would force twinBase < mono).

    lines 322–364

    uses mono_le_of_optimal, mono_sigma', avg, mono_G_ge, base_le_mono, base_lt_mono

    private theorem rigidity (ρ : PW → Fin 3) (hopt : is_maxcut_optimal maxcut_pinned_twins_graph ρ) :
        ∃ p : Equiv.Perm (Fin 3), ρ = fun v => p (maxcut_anchor_three_initial_coloring v.1) := by
      classical
      have hMpos : 0 < Fintype.card (PV → Fin 2) := Fintype.card_pos
      have hup : mono maxcut_pinned_twins_graph ρ ≤ 192 := by
        have h := mono_le_of_optimal maxcut_pinned_twins_graph ρ
          (fun v => maxcut_anchor_three_initial_coloring v.1) hopt
        rw [mono_sigma'] at h
        exact h
      have havg := avg ρ
      have hge : Fintype.card (PV → Fin 2) * 48 ≤
          ∑ c : PV → Fin 2, mono maxcut_anchor_three_graph (slice ρ c) := by
        have h := Finset.sum_le_sum (fun c (_ : c ∈ (Finset.univ : Finset (PV → Fin 2))) =>
          mono_G_ge (slice ρ c))
        simpa [Finset.sum_const, Finset.card_univ, mul_comm] using h
      have hbase_ge : 192 ≤ twinBase ρ := by
        by_contra h
        push Not at h
        have h2 : Fintype.card (PV → Fin 2) * twinBase ρ < Fintype.card (PV → Fin 2) * 192 :=
          Nat.mul_lt_mul_of_pos_left h hMpos
        generalize Fintype.card (PV → Fin 2) * twinBase ρ = q at havg h2
        omega
      have hall : ∀ c, mono maxcut_anchor_three_graph (slice ρ c) ≤ 48 := by
        intro c
        by_contra h
        push Not at h
        have hlt : Fintype.card (PV → Fin 2) * 48 <
            ∑ c : PV → Fin 2, mono maxcut_anchor_three_graph (slice ρ c) := by
          have h' := Finset.sum_lt_sum
            (fun c' (_ : c' ∈ (Finset.univ : Finset (PV → Fin 2))) => mono_G_ge (slice ρ c'))
            ⟨c, Finset.mem_univ _, h⟩
          simpa [Finset.sum_const, Finset.card_univ, mul_comm] using h'
        have hb := base_le_mono ρ
        have h3 : Fintype.card (PV → Fin 2) * twinBase ρ ≤ Fintype.card (PV → Fin 2) * 192 :=
          Nat.mul_le_mul_left _ (hb.trans hup)
        generalize Fintype.card (PV → Fin 2) * twinBase ρ = q at havg h3
        omega
      have hnopin : ∀ (u : Fin 16) (s : Fin 2) (j : Fin 3),
          j ≠ maxcut_anchor_three_initial_coloring (.inl u) →
          ρ (.inr (j, 24), 0) ≠ ρ (.inl u, s) := by
        intro u s j hj heq
        have h := base_lt_mono ρ u s j hj heq
        omega
  13. Both twin copies of every anchor vertex are colored identically by a single color permutation p.

    Each slice has mono = 48 < 50, so anchor rigidity applies to each slice. The constant slice c ≡ 0 gives a permutation p with ρ(inr(j, i), 0) = p(j). Updating the slice assignment at a single anchor vertex (j, i) to twin copy 1 while leaving another anchor vertex in the same class at copy 0 forces the permutation for the modified slice to agree with p, showing ρ(inr(j, i), 1) = p(j) as well.

    lines 365–385

    uses anchor_rigidity, Function.update_self, Function.update_of_ne

      have hanc : ∀ c : PV → Fin 2, ∃ p : Equiv.Perm (Fin 3),
          ∀ j i, ρ (.inr (j, i), c (.inr (j, i))) = p j := by
        intro c
        exact anchor_rigidity (slice ρ c) (by have := hall c; omega)
      obtain ⟨p, hp⟩ := hanc (fun _ => 0)
      have hA : ∀ (j : Fin 3) (i : Fin 25) (s : Fin 2), ρ (.inr (j, i), s) = p j := by
        intro j i s
        obtain ⟨q, hq⟩ := hanc (Function.update (fun _ => 0) (.inr (j, i)) s)
        let i' : Fin 25 := if i.val = 0 then 1 else 0
        have hi' : (Sum.inr (j, i') : PV) ≠ Sum.inr (j, i) := by
          intro h
          have h' : i' = i := (Prod.mk.inj (Sum.inr.inj h)).2
          have hv := congrArg Fin.val h'
          simp only [i'] at hv
          split_ifs at hv with h0 <;> simp at hv <;> omega
        have h1 := hq j i
        have h2 := hq j i'
        have h3 := hp j i'
        rw [Function.update_self] at h1
        rw [Function.update_of_ne hi'] at h2
        exact h1.trans (h2.symm.trans h3)
  14. Every core vertex twin has color p(initial coloring), completing the rigidity theorem.

    If some core vertex twin (u, s) had a color different from p(initial(u)), the inverse permutation would identify an anchor color j ≠ initial(u) such that the pinning edge from (u, s) to (inr(j, 24), 0) is monochromatic. This contradicts the fact that no pinning edge is monochromatic. Therefore, all core and anchor vertices match the permuted doubled initial coloring.

    lines 386–404

      have hC : ∀ (u : Fin 16) (s : Fin 2),
          ρ (.inl u, s) = p (maxcut_anchor_three_initial_coloring (.inl u)) := by
        intro u s
        by_contra hne
        have hc : p (p.symm (ρ (.inl u, s))) = ρ (.inl u, s) := p.apply_symm_apply _
        have hcj : p.symm (ρ (.inl u, s)) ≠ maxcut_anchor_three_initial_coloring (.inl u) := by
          intro h
          apply hne
          rw [← hc, h]
        exact hnopin u s _ hcj (by rw [hA _ 24 0, hc])
      refine ⟨p, ?_⟩
      funext x
      rcases x with ⟨v, s⟩
      cases v with
      | inl u => exact hC u s
      | inr ji =>
        obtain ⟨j, i⟩ := ji
        exact hA j i s
    
SimpleGraph.fromRel_adj
For a simple graph constructed from a relation r, v and w are adjacent iff they are distinct and either r v w or r w v holds.
maxcut_utility_add_monochromatic_card
For any vertex v in a graph G under coloring σ, the cut utility of v plus the number of monochromatic edges incident to v equals the degree of v.
welfare_add_mono
For any graph H and 3-coloring ρ, the Max-Cut welfare plus the monochromatic directed edge count equals the sum of all vertex degrees.
Finset.sum_add_sum_compl
The sum of a function over a subset s plus the sum over its complement sᶜ equals the sum over the entire universe.
mono_sum
The monochromatic count mono H ρ equals the double sum over all vertices v and w of the indicator that v is adjacent to w and ρ w = ρ v.
independent_mono_bound
For an independent set S, twice the sum of monochromatic degrees in S is at most the total monochromatic edge count of the graph.
exists_good_of_independent
If an independent set S satisfies mono H ρ < 2 * |S|, then some vertex in S has no incident monochromatic edges.
anchor_adj
Two anchor vertices (j, i) and (l, t) are adjacent in G₃ if and only if j ≠ l.
mono_sigma
The monochromatic directed edge count of the initial coloring on the anchor-3 graph G₃ is 48.
maxcut_anchor_three_initial_optimal
The initial coloring of the anchor-3 graph G₃ maximizes Max-Cut welfare.
mono_le_of_optimal
Any Max-Cut optimal coloring achieves a monochromatic directed edge count less than or equal to that of any other coloring.
mono_G_ge
Every 3-coloring of the anchor-3 graph G₃ has monochromatic count at least 48.
anchor_rigidity
Any 3-coloring of G₃ with monochromatic count less than 50 is constant on each anchor color class, given by a permutation of the colors.
lift_adj
If two vertices are adjacent in G₃, all four pairs of their twin copies are adjacent in the pinned twins graph.
adj_iff
Two vertices in the pinned twins graph are adjacent iff they are distinct and either their base vertices are adjacent in G₃ or they are connected by a pinning edge.
pin_ne
A pinning edge only connects vertices whose initial colors in G₃ are distinct.
pin_adj
For any core vertex u, twin copy s, and color j different from u's initial color, there is an edge to anchor vertex (j, 24, 0) in the pinned twins graph that was not present in G₃.
ind_le
For any pair of twin vertices, the indicator that their base vertices form a monochromatic edge in G₃ is bounded by the indicator that they form a monochromatic edge in the pinned twins graph.
base_le_mono
The total monochromatic count from base edges (twinBase) is at most the total monochromatic count in the pinned twins graph.
base_lt_mono
If any pinning edge is monochromatic, then twinBase is strictly less than the total monochromatic count.
base_split
The twinBase count decomposes as the sum over all base vertex pairs v, w and twin indices s, t of the indicator that v ~ w in G₃ and ρ(w, t) = ρ(v, s).
pair_avg
For distinct vertices v ≠ w, four times the sum of F(c(v), c(w)) over all slices c equals 2^|X| times the sum of F(s, t) over all four twin pairs (s, t).
mono_sigma'
The doubled initial coloring on the pinned twins graph has monochromatic count exactly 192.
avg
Four times the sum of monochromatic counts over all 2^|PV| slices in G₃ equals 2^|PV| times the twinBase count.
Function.update_self
Updating a function f at point a with value v and evaluating at a yields v.
Function.update_of_ne
Updating a function f at point a' with value v and evaluating at a ≠ a' yields f(a).

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

set_option maxRecDepth 200000set_option maxHeartbeats 0set_option synthInstance.maxSize 200000open scoped BigOperatorsnamespace MaxcutPinnedTwinsRigidityprivate abbrev PV := Fin 16 ⊕ (Fin 3 × Fin 25)private abbrev PW := PV × Fin 2private instance maxcut_pinned_twins_optimum_rigidity_base_dec : DecidableRel maxcut_anchor_three_graph.Adj := by  unfold maxcut_anchor_three_graph; infer_instanceprivate instance maxcut_pinned_twins_optimum_rigidity_pinned_dec : DecidableRel maxcut_pinned_twins_graph.Adj := by  unfold maxcut_pinned_twins_graph; infer_instanceprivate lemma lift_adj (a b : PW) (h : maxcut_anchor_three_graph.Adj a.1 b.1) :    maxcut_pinned_twins_graph.Adj a b := by  simp only [maxcut_pinned_twins_graph, SimpleGraph.fromRel_adj]  exact ⟨fun hab => h.ne (congrArg Prod.fst hab), Or.inl (Or.inl h)⟩private def pin (a b : PW) : Prop :=  match a.1, b.1 with  | .inl i, .inr (j, x) => x.val = 24 ∧ b.2.val = 0 ∧      j ≠ maxcut_anchor_three_initial_coloring (.inl i)  | _, _ => Falseprivate lemma adj_iff (a b : PW) : maxcut_pinned_twins_graph.Adj a b ↔    a ≠ b ∧ ((maxcut_anchor_three_graph.Adj a.1 b.1 ∨ pin a b) ∨      (maxcut_anchor_three_graph.Adj b.1 a.1 ∨ pin b a)) := Iff.rflprivate lemma pin_ne (a b : PW) (h : pin a b) :    maxcut_anchor_three_initial_coloring b.1 ≠ maxcut_anchor_three_initial_coloring a.1 := by  rcases a with ⟨a1, a2⟩  rcases b with ⟨b1, b2⟩  cases a1 with  | inl i =>    cases b1 with    | inl i' => exact h.elim    | inr jx =>      obtain ⟨j, x⟩ := jx      exact h.2.2  | inr jx => exact h.elimprivate lemma pin_adj : ∀ (u : Fin 16) (s : Fin 2) (j : Fin 3),    j ≠ maxcut_anchor_three_initial_coloring (.inl u) →    maxcut_pinned_twins_graph.Adj (.inl u, s) (.inr (j, 24), 0) ∧    ¬ maxcut_anchor_three_graph.Adj (.inl u) (.inr (j, 24)) := by  decideprivate def mono {X : Type} [Fintype X] (H : SimpleGraph X) [DecidableRel H.Adj] (ρ : X → Fin 3) : ℕ :=  ∑ v, (Finset.univ.filter fun w => H.Adj v w ∧ ρ w = ρ v).cardprivate lemma mono_sum {X : Type} [Fintype X] (H : SimpleGraph X) [DecidableRel H.Adj] (ρ : X → Fin 3) :    mono H ρ = ∑ v, ∑ w, if H.Adj v w ∧ ρ w = ρ v then 1 else 0 := by  simp only [mono, Finset.card_filter]private lemma welfare_add_mono {X : Type} [Fintype X] (H : SimpleGraph X) [DecidableRel H.Adj]    (ρ : X → Fin 3) : maxcut_welfare H ρ + mono H ρ = ∑ v, H.degree v := by  rw [maxcut_welfare, mono, ← Finset.sum_add_distrib]  exact Finset.sum_congr rfl fun v _ => maxcut_utility_add_monochromatic_card H ρ vprivate lemma mono_le_of_optimal {X : Type} [Fintype X] (H : SimpleGraph X) [DecidableRel H.Adj]    (ρ τ : X → Fin 3) (h : is_maxcut_optimal H ρ) : mono H ρ ≤ mono H τ := by  have h1 := h τ  have h2 := welfare_add_mono H ρ  have h3 := welfare_add_mono H τ  omegaprivate lemma independent_mono_bound {X : Type} [Fintype X] [DecidableEq X]    (H : SimpleGraph X) [DecidableRel H.Adj] (ρ : X → Fin 3)    (S : Finset X) (hind : ∀ v ∈ S, ∀ w ∈ S, ¬ H.Adj v w) :    2 * (∑ v ∈ S, (Finset.univ.filter fun w => H.Adj v w ∧ ρ w = ρ v).card)      ≤ mono H ρ := by  classical  let f : X → X → ℕ := fun v w => if H.Adj v w ∧ ρ w = ρ v then 1 else 0  have hsym (v w : X) : f v w = f w v := by    dsimp [f]    congr 1    exact propext ⟨fun h => ⟨h.1.symm, h.2.symm⟩, fun h => ⟨h.1.symm, h.2.symm⟩⟩  have hzero : ∑ v ∈ S, ∑ w ∈ S, f v w = 0 := by    apply Finset.sum_eq_zero    intro v hv    apply Finset.sum_eq_zero    intro w hw    simp [f, hind v hv w hw]  have hcross : ∑ v ∈ Sᶜ, ∑ w ∈ S, f v w = ∑ v ∈ S, ∑ w ∈ Sᶜ, f v w := by    rw [Finset.sum_comm]    exact Finset.sum_congr rfl fun v _ => Finset.sum_congr rfl fun w _ => hsym w v  have hsplit (v : X) : ∑ w, f v w = ∑ w ∈ S, f v w + ∑ w ∈ Sᶜ, f v w :=    (Finset.sum_add_sum_compl S _).symm  have hall : mono H ρ =      2 * (∑ v ∈ S, ∑ w ∈ Sᶜ, f v w) + ∑ v ∈ Sᶜ, ∑ w ∈ Sᶜ, f v w := by    rw [mono_sum]    change (∑ v, ∑ w, f v w) = _    rw [← Finset.sum_add_sum_compl S]    simp only [hsplit, Finset.sum_add_distrib, hzero, hcross]    omega  have hpart : (∑ v ∈ S, (Finset.univ.filter fun w => H.Adj v w ∧ ρ w = ρ v).card) =      ∑ v ∈ S, ∑ w ∈ Sᶜ, f v w := by    simp only [Finset.card_filter]    change (∑ v ∈ S, ∑ w, f v w) = _    simp only [hsplit, Finset.sum_add_distrib, hzero, zero_add]  rw [hpart, hall]  omegaprivate lemma exists_good_of_independent {X : Type} [Fintype X] [DecidableEq X]    (H : SimpleGraph X) [DecidableRel H.Adj] (ρ : X → Fin 3)    (S : Finset X) (hind : ∀ v ∈ S, ∀ w ∈ S, ¬ H.Adj v w)    (hsmall : mono H ρ < 2 * S.card) :    ∃ v ∈ S, ∀ w, H.Adj v w → ρ w ≠ ρ v := by  classical  by_contra h  push Not at h  have hpos : ∀ v ∈ S, 1 ≤ (Finset.univ.filter fun w => H.Adj v w ∧ ρ w = ρ v).card := by    intro v hv    obtain ⟨w, hadj, hc⟩ := h v hv    exact Finset.card_pos.mpr ⟨w, by simp [hadj, hc]⟩  have hsum := Finset.sum_le_sum hpos  have hb := independent_mono_bound H ρ S hind  simp only [Finset.sum_const, smul_eq_mul, mul_one] at hsum  omegaprivate lemma anchor_adj (j l : Fin 3) (i t : Fin 25) :    maxcut_anchor_three_graph.Adj (.inr (j,i)) (.inr (l,t)) ↔ j ≠ l := by  change ((Sum.inr (j,i) : PV) ≠ Sum.inr (l,t) ∧ (j ≠ l ∨ l ≠ j)) ↔ j ≠ l  constructor  · rintro ⟨_, h | h⟩    · exact h    · exact h.symm  · intro h    refine ⟨?_, Or.inl h⟩    intro heq    exact h (congrArg Prod.fst (Sum.inr.inj heq))private lemma mono_sigma :    mono maxcut_anchor_three_graph maxcut_anchor_three_initial_coloring = 48 := by  decideprivate lemma mono_G_ge (ρ : PV → Fin 3) : 48 ≤ mono maxcut_anchor_three_graph ρ := by  have h := mono_le_of_optimal maxcut_anchor_three_graph maxcut_anchor_three_initial_coloring ρ    maxcut_anchor_three_initial_optimal  rw [mono_sigma] at h  exact hprivate lemma anchor_rigidity (ρ : PV → Fin 3) (hsmall : mono maxcut_anchor_three_graph ρ < 50) :    ∃ p : Equiv.Perm (Fin 3), ∀ j i, ρ (.inr (j,i)) = p j := by  classical  have hgood : ∀ j : Fin 3, ∃ i : Fin 25,      ∀ w, maxcut_anchor_three_graph.Adj (.inr (j,i)) w → ρ w ≠ ρ (.inr (j,i)) := by    intro j    let S : Finset PV := Finset.univ.image fun i : Fin 25 => Sum.inr (j,i)    have hcard : S.card = 25 := by      rw [Finset.card_image_of_injective _ (by intro a b h; simpa using h)]      decide    have hind : ∀ v ∈ S, ∀ w ∈ S, ¬ maxcut_anchor_three_graph.Adj v w := by      intro v hv w hw      obtain ⟨i, _, rfl⟩ := Finset.mem_image.mp hv      obtain ⟨t, _, rfl⟩ := Finset.mem_image.mp hw      simp [anchor_adj]    obtain ⟨v, hv, hg⟩ := exists_good_of_independent maxcut_anchor_three_graph ρ S hind      (by omega)    obtain ⟨i, _, rfl⟩ := Finset.mem_image.mp hv    exact ⟨i, hg⟩  choose gi hg using hgood  let c : Fin 3 → Fin 3 := fun j => ρ (.inr (j, gi j))  have hi : Function.Injective c := by    intro j l heq    by_contra hne    exact hg j (.inr (l, gi l)) ((anchor_adj j l _ _).2 hne) heq.symm  have hb : Function.Bijective c := (Fintype.bijective_iff_injective_and_card c).2 ⟨hi, rfl⟩  refine ⟨Equiv.ofBijective c hb, ?_⟩  intro j i  obtain ⟨l, hl⟩ := hb.2 (ρ (.inr (j,i)))  have heq : l = j := by    by_contra hne    exact hg l (.inr (j,i)) ((anchor_adj l j _ _).2 hne) hl.symm  subst l  exact hl.symm/-- Monochromatic ordered pairs of the twin graph that come from edges of `G_3`. -/private def twinBase (ρ : PW → Fin 3) : ℕ :=  ∑ a : PW, ∑ b : PW, if maxcut_anchor_three_graph.Adj a.1 b.1 ∧ ρ b = ρ a then 1 else 0private lemma base_split (ρ : PW → Fin 3) : twinBase ρ = ∑ v : PV, ∑ w : PV, ∑ s : Fin 2, ∑ t : Fin 2,    if maxcut_anchor_three_graph.Adj v w ∧ ρ (w, t) = ρ (v, s) then 1 else 0 := by  unfold twinBase  simp only [Fintype.sum_prod_type]  exact Finset.sum_congr rfl fun v _ => Finset.sum_commprivate lemma ind_le (ρ : PW → Fin 3) (a b : PW) :    (if maxcut_anchor_three_graph.Adj a.1 b.1 ∧ ρ b = ρ a then 1 else 0) ≤      (if maxcut_pinned_twins_graph.Adj a b ∧ ρ b = ρ a then 1 else 0) := by  by_cases h : maxcut_anchor_three_graph.Adj a.1 b.1 ∧ ρ b = ρ a  · rw [if_pos h, if_pos ⟨lift_adj a b h.1, h.2⟩]  · rw [if_neg h]    exact Nat.zero_le _private lemma base_le_mono (ρ : PW → Fin 3) : twinBase ρ ≤ mono maxcut_pinned_twins_graph ρ := by  rw [mono_sum]  exact Finset.sum_le_sum fun a _ => Finset.sum_le_sum fun b _ => ind_le ρ a bprivate lemma base_lt_mono (ρ : PW → Fin 3) (u : Fin 16) (s : Fin 2) (j : Fin 3)    (hj : j ≠ maxcut_anchor_three_initial_coloring (.inl u))    (heq : ρ (.inr (j, 24), 0) = ρ (.inl u, s)) :    twinBase ρ < mono maxcut_pinned_twins_graph ρ := by  rw [mono_sum]  apply Finset.sum_lt_sum  · exact fun a _ => Finset.sum_le_sum fun b _ => ind_le ρ a b  · refine ⟨(.inl u, s), Finset.mem_univ _, ?_⟩    apply Finset.sum_lt_sum    · exact fun b _ => ind_le ρ _ b    · refine ⟨(.inr (j, 24), 0), Finset.mem_univ _, ?_⟩      obtain ⟨hadj, hnot⟩ := pin_adj u s j hj      rw [if_neg (fun h => hnot h.1), if_pos ⟨hadj, heq⟩]      exact Nat.zero_lt_oneprivate lemma mono_sigma' :    mono maxcut_pinned_twins_graph (fun v => maxcut_anchor_three_initial_coloring v.1) = 192 := by  have hpt : ∀ a b : PW,      (if maxcut_pinned_twins_graph.Adj a b ∧ maxcut_anchor_three_initial_coloring b.1 =          maxcut_anchor_three_initial_coloring a.1 then 1 else 0) =      (if maxcut_anchor_three_graph.Adj a.1 b.1 ∧ maxcut_anchor_three_initial_coloring b.1 =          maxcut_anchor_three_initial_coloring a.1 then 1 else 0) := by    intro a b    congr 1    apply propext    constructor    · rintro ⟨hadj, hc⟩      refine ⟨?_, hc⟩      rcases (adj_iff a b).1 hadj with ⟨_, (h | h) | (h | h)⟩      · exact h      · exact absurd hc (pin_ne a b h)      · exact h.symm      · exact absurd hc.symm (pin_ne b a h)    · rintro ⟨hadj, hc⟩      exact ⟨lift_adj a b hadj, hc⟩  rw [mono_sum]  simp only [hpt]  change twinBase (fun v => maxcut_anchor_three_initial_coloring v.1) = 192  rw [base_split]  have h48 := mono_sigma  rw [mono_sum] at h48  rw [show (192 : ℕ) = 4 * 48 from rfl, ← h48, Finset.mul_sum]  apply Finset.sum_congr rfl  intro v _  rw [Finset.mul_sum]  apply Finset.sum_congr rfl  intro w _  simp only [Fin.sum_univ_two]  ringprivate def slice (ρ : PW → Fin 3) (c : PV → Fin 2) : PV → Fin 3 := fun v => ρ (v, c v)private lemma pair_avg {X : Type} [Fintype X] [DecidableEq X] (v w : X) (hvw : v ≠ w)    (Fv : Fin 2 → Fin 2 → ℕ) :    4 * ∑ c : X → Fin 2, Fv (c v) (c w) = Fintype.card (X → Fin 2) * ∑ s, ∑ t, Fv s t := by  have hz : ∀ z a : Fin 2, z + a + a = z := by decide  have key : ∀ a b : Fin 2, ∑ c : X → Fin 2, Fv (c v + a) (c w + b) =      ∑ c : X → Fin 2, Fv (c v) (c w) := by    intro a b    let e : (X → Fin 2) → (X → Fin 2) := fun c x =>      if x = v then c x + a else if x = w then c x + b else c x    have he : Function.Involutive e := by      intro c      funext x      simp only [e]      by_cases h1 : x = v      · simp [h1, hz]      · by_cases h2 : x = w        · simp [h2, Ne.symm hvw, hz]        · simp [h1, h2]    have hev : ∀ c, e c v = c v + a := by intro c; simp [e]    have hew : ∀ c, e c w = c w + b := by intro c; simp [e, Ne.symm hvw]    calc ∑ c : X → Fin 2, Fv (c v + a) (c w + b)        = ∑ c : X → Fin 2, (fun d : X → Fin 2 => Fv (d v) (d w))            (Function.Involutive.toPerm e he c) := by          apply Finset.sum_congr rfl          intro c _          simp only [Function.Involutive.coe_toPerm, hev, hew]      _ = ∑ c : X → Fin 2, Fv (c v) (c w) := Equiv.sum_comp (Function.Involutive.toPerm e he) (fun d : X → Fin 2 => Fv (d v) (d w))  have hinner : ∀ c : X → Fin 2, ∑ a : Fin 2, ∑ b : Fin 2, Fv (c v + a) (c w + b) =      ∑ s, ∑ t, Fv s t := by    intro c    have h1 := Equiv.sum_comp (Equiv.addLeft (c v)) (fun s => ∑ t, Fv s t)    rw [← h1]    apply Finset.sum_congr rfl    intro a _    exact (Equiv.sum_comp (Equiv.addLeft (c w)) (fun t => Fv (c v + a) t))  calc 4 * ∑ c : X → Fin 2, Fv (c v) (c w)      = ∑ a : Fin 2, ∑ b : Fin 2, ∑ c : X → Fin 2, Fv (c v + a) (c w + b) := by        simp only [key, Finset.sum_const, Finset.card_univ, Fintype.card_fin, smul_eq_mul]        ring    _ = ∑ a : Fin 2, ∑ c : X → Fin 2, ∑ b : Fin 2, Fv (c v + a) (c w + b) :=        Finset.sum_congr rfl (fun a _ => Finset.sum_comm)    _ = ∑ c : X → Fin 2, ∑ a : Fin 2, ∑ b : Fin 2, Fv (c v + a) (c w + b) := Finset.sum_comm    _ = ∑ c : X → Fin 2, ∑ s, ∑ t, Fv s t := Finset.sum_congr rfl (fun c _ => hinner c)    _ = Fintype.card (X → Fin 2) * ∑ s, ∑ t, Fv s t := by        simp only [Finset.sum_const, Finset.card_univ, smul_eq_mul]private lemma avg (ρ : PW → Fin 3) :    4 * ∑ c : PV → Fin 2, mono maxcut_anchor_three_graph (slice ρ c) =      Fintype.card (PV → Fin 2) * twinBase ρ := by  simp only [mono_sum, slice]  rw [base_split]  have hswap : ∀ I : (PV → Fin 2) → PV → PV → ℕ,      ∑ c, ∑ v, ∑ w, I c v w = ∑ v, ∑ w, ∑ c, I c v w := by    intro I    rw [Finset.sum_comm]    exact Finset.sum_congr rfl fun v _ => Finset.sum_comm  rw [hswap, Finset.mul_sum, Finset.mul_sum]  apply Finset.sum_congr rfl  intro v _  rw [Finset.mul_sum, Finset.mul_sum]  apply Finset.sum_congr rfl  intro w _  by_cases hvw : maxcut_anchor_three_graph.Adj v w  · simp only [hvw, true_and]    exact pair_avg v w hvw.ne (fun s t => if ρ (w, t) = ρ (v, s) then 1 else 0)  · simp [hvw]private theorem rigidity (ρ : PW → Fin 3) (hopt : is_maxcut_optimal maxcut_pinned_twins_graph ρ) :    ∃ p : Equiv.Perm (Fin 3), ρ = fun v => p (maxcut_anchor_three_initial_coloring v.1) := by  classical  have hMpos : 0 < Fintype.card (PV → Fin 2) := Fintype.card_pos  have hup : mono maxcut_pinned_twins_graph ρ ≤ 192 := by    have h := mono_le_of_optimal maxcut_pinned_twins_graph ρ      (fun v => maxcut_anchor_three_initial_coloring v.1) hopt    rw [mono_sigma'] at h    exact h  have havg := avg ρ  have hge : Fintype.card (PV → Fin 2) * 48 ≤      ∑ c : PV → Fin 2, mono maxcut_anchor_three_graph (slice ρ c) := by    have h := Finset.sum_le_sum (fun c (_ : c ∈ (Finset.univ : Finset (PV → Fin 2))) =>      mono_G_ge (slice ρ c))    simpa [Finset.sum_const, Finset.card_univ, mul_comm] using h  have hbase_ge : 192 ≤ twinBase ρ := by    by_contra h    push Not at h    have h2 : Fintype.card (PV → Fin 2) * twinBase ρ < Fintype.card (PV → Fin 2) * 192 :=      Nat.mul_lt_mul_of_pos_left h hMpos    generalize Fintype.card (PV → Fin 2) * twinBase ρ = q at havg h2    omega  have hall : ∀ c, mono maxcut_anchor_three_graph (slice ρ c) ≤ 48 := by    intro c    by_contra h    push Not at h    have hlt : Fintype.card (PV → Fin 2) * 48 <        ∑ c : PV → Fin 2, mono maxcut_anchor_three_graph (slice ρ c) := by      have h' := Finset.sum_lt_sum        (fun c' (_ : c' ∈ (Finset.univ : Finset (PV → Fin 2))) => mono_G_ge (slice ρ c'))        ⟨c, Finset.mem_univ _, h⟩      simpa [Finset.sum_const, Finset.card_univ, mul_comm] using h'    have hb := base_le_mono ρ    have h3 : Fintype.card (PV → Fin 2) * twinBase ρ ≤ Fintype.card (PV → Fin 2) * 192 :=      Nat.mul_le_mul_left _ (hb.trans hup)    generalize Fintype.card (PV → Fin 2) * twinBase ρ = q at havg h3    omega  have hnopin : ∀ (u : Fin 16) (s : Fin 2) (j : Fin 3),      j ≠ maxcut_anchor_three_initial_coloring (.inl u) →      ρ (.inr (j, 24), 0) ≠ ρ (.inl u, s) := by    intro u s j hj heq    have h := base_lt_mono ρ u s j hj heq    omega  have hanc : ∀ c : PV → Fin 2, ∃ p : Equiv.Perm (Fin 3),      ∀ j i, ρ (.inr (j, i), c (.inr (j, i))) = p j := by    intro c    exact anchor_rigidity (slice ρ c) (by have := hall c; omega)  obtain ⟨p, hp⟩ := hanc (fun _ => 0)  have hA : ∀ (j : Fin 3) (i : Fin 25) (s : Fin 2), ρ (.inr (j, i), s) = p j := by    intro j i s    obtain ⟨q, hq⟩ := hanc (Function.update (fun _ => 0) (.inr (j, i)) s)    let i' : Fin 25 := if i.val = 0 then 1 else 0    have hi' : (Sum.inr (j, i') : PV) ≠ Sum.inr (j, i) := by      intro h      have h' : i' = i := (Prod.mk.inj (Sum.inr.inj h)).2      have hv := congrArg Fin.val h'      simp only [i'] at hv      split_ifs at hv with h0 <;> simp at hv <;> omega    have h1 := hq j i    have h2 := hq j i'    have h3 := hp j i'    rw [Function.update_self] at h1    rw [Function.update_of_ne hi'] at h2    exact h1.trans (h2.symm.trans h3)  have hC : ∀ (u : Fin 16) (s : Fin 2),      ρ (.inl u, s) = p (maxcut_anchor_three_initial_coloring (.inl u)) := by    intro u s    by_contra hne    have hc : p (p.symm (ρ (.inl u, s))) = ρ (.inl u, s) := p.apply_symm_apply _    have hcj : p.symm (ρ (.inl u, s)) ≠ maxcut_anchor_three_initial_coloring (.inl u) := by      intro h      apply hne      rw [← hc, h]    exact hnopin u s _ hcj (by rw [hA _ 24 0, hc])  refine ⟨p, ?_⟩  funext x  rcases x with ⟨v, s⟩  cases v with  | inl u => exact hC u s  | inr ji =>    obtain ⟨j, i⟩ := ji    exact hA j i send MaxcutPinnedTwinsRigiditytheorem maxcut_pinned_twins_optimum_rigidity :    ∀ ρ : ((Fin 16 ⊕ (Fin 3 × Fin 25)) × Fin 2) → Fin 3,      is_maxcut_optimal maxcut_pinned_twins_graph ρ →      ∃ p : Equiv.Perm (Fin 3),        ρ = fun v => p (maxcut_anchor_three_initial_coloring v.1) := MaxcutPinnedTwinsRigidity.rigidity
See it in the graphDiscuss this resultChallenge it