AFTD Auto-Formalizing Theoretical Domains

op_258_bounded_extension

theoremverified

For a positive antitone profile a with Σ a i > 1 there is n₀ such that for every n ≥ n₀, every partially defined a-bounded colouring of the edges of K_n (i.e. the coloured edge set s has fibres of size at most a i * C(n,2)) extends to a full a-bounded colouring of all edges of K_n agreeing with it on s.

Statement

theorem op_258_bounded_extension (a : ℕ+ → ℝ) (hpos : ∀ i, 0 < a i) (hanti : Antitone a)
    (hsum : 1 < ∑' i : ℕ+, ENNReal.ofReal (a i)) :
    ∃ n₀ : ℕ, ∀ n ≥ n₀, ∀ (s : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet)
      (c₀ : (SimpleGraph.completeGraph (Fin n)).edgeSet → ℕ+),
      (∀ i : ℕ+, ((s.filter (fun e => c₀ e = i)).card : ℝ) ≤ a i * (n.choose 2 : ℝ)) →
      ∃ c : (SimpleGraph.completeGraph (Fin n)).edgeSet → ℕ+,
        op_258_bounded a n c ∧ ∀ e ∈ s, c e = c₀ e
Source
step towards op_258_forces_step
Verified
21 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • op_258_exists_finset_sum_gt_oneIf f : α → ℝ is nonnegative and its ENNReal-sum of ENNReal.ofReal (f ·) is strictly greater than 1, then some finite set I of indices and…
  • op_258_boundedA colouring c of the edges of the complete graph K_n is a-bounded if for every colour i the number of edges of colour i is at most a i *…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
Used by 1

The proof, explained

The argument proceeds by first establishing a combinatorial lemma: any subset T of edges can be partitioned into color classes respecting prescribed integer capacities, provided the sum of capacities is at least |T|. To extend a partial a-bounded edge coloring on s ⊆ E(K_n), we choose a finite set of colors I whose sum of profile weights strictly exceeds 1 by some δ > 0. For large n, the total remaining capacity ∑_{i ∈ I} (⌊a_i * C(n, 2)⌋ - |s ∩ c₀⁻¹(i)|) is bounded below by (1 + δ) * C(n, 2) - |I| - |s|, which exceeds the number of uncolored edges C(n, 2) - |s| because |I| ≤ δ * C(n, 2). Applying the combinatorial lemma colors all remaining edges while strictly respecting the capacity bounds, yielding the desired extension.

  1. The capacity-bounded coloring lemma holds when the set T to be colored is empty.

    We proceed by induction on the finite set T, generalizing over the capacity function cap. In the base case where T = ∅, any assignment works; we assign the constant color 1 to all vertices. For every color i, the fiber in ∅ is empty, so its cardinality is 0, which is at most cap(i).

    lines 5–10

    uses Finset.induction

      classical
      intro cap T
      induction T using Finset.induction generalizing cap with
      | empty =>
          intro _
          exact ⟨fun _ => 1, fun i => by simp⟩
  2. In the inductive step T ∪ {x}, at least one color in I has strictly positive capacity.

    Assuming |T ∪ {x}| ≤ ∑_{i ∈ I} cap(i) with x ∉ T, the cardinality |T ∪ {x}| = |T| + 1 is positive, so the sum of capacities is strictly positive. If every capacity in I were zero, the sum would be zero; thus by contradiction there exists some color i₀ ∈ I with cap(i₀) > 0.

    lines 11–25

    uses Finset.card_insert_of_notMem, Nat.eq_zero_or_pos, Finset.sum_eq_zero

      | insert x T hx ih =>
          intro h
          have hpos : 0 < ∑ i ∈ I, cap i := by
            have hc : (insert x T).card = T.card + 1 := Finset.card_insert_of_notMem hx
            omega
          have hex : ∃ i ∈ I, 0 < cap i := by
            by_contra hcon
            have hz : ∀ i ∈ I, cap i = 0 := by
              intro i hi
              rcases Nat.eq_zero_or_pos (cap i) with h' | h'
              · exact h'
              · exact absurd ⟨i, hi, h'⟩ hcon
            have : ∑ i ∈ I, cap i = 0 := Finset.sum_eq_zero hz
            omega
          obtain ⟨i₀, hi₀mem, hi₀pos⟩ := hex
  3. Decreasing the capacity of i₀ by 1 yields an admissible capacity function cap' for T, producing a valid coloring f' on T.

    We define cap' to agree with cap everywhere except at i₀, where cap'(i₀) = cap(i₀) - 1. Since |T ∪ {x}| = |T| + 1 and the sum of capacities over I decreases by exactly 1, we obtain |T| ≤ ∑_{i ∈ I} cap'(i). Applying the induction hypothesis to T and cap' gives a coloring f' on T whose fibers satisfy |T ∩ f'⁻¹(i)| ≤ cap'(i) for all i.

    lines 26–34

    uses Finset.sdiff_singleton_eq_erase, Finset.sum_update_of_mem, Finset.add_sum_erase, Finset.card_insert_of_notMem

          set cap' : ℕ+ → ℕ := Function.update cap i₀ (cap i₀ - 1) with hcap'def
          have hsum' : T.card ≤ ∑ i ∈ I, cap' i := by
            have hsub : I \ {i₀} = I.erase i₀ := Finset.sdiff_singleton_eq_erase i₀ I
            rw [hcap'def, Finset.sum_update_of_mem hi₀mem, hsub]
            have hkey : cap i₀ + ∑ x ∈ I.erase i₀, cap x = ∑ x ∈ I, cap x :=
              Finset.add_sum_erase I cap hi₀mem
            have hc : (insert x T).card = T.card + 1 := Finset.card_insert_of_notMem hx
            omega
          obtain ⟨f', hf'⟩ := ih cap' hsum'
  4. Extending f' by setting f(x) = i₀ satisfies the capacity bound for color i₀ on T ∪ {x}.

    We define f to equal i₀ at x and f' on T. For color i = i₀, the fiber in T ∪ {x} contains x together with the elements of T where f' took value i₀. Since x ∉ T, its cardinality is |T ∩ f'⁻¹(i₀)| + 1. By the inductive property of f', this is at most cap'(i₀) + 1 = (cap(i₀) - 1) + 1 = cap(i₀).

    lines 35–52

    uses Finset.filter_insert, Finset.filter_congr, Function.update_of_ne, Finset.card_insert_of_notMem, Function.update_self

          refine ⟨Function.update f' x i₀, ?_⟩
          intro i
          by_cases hii : i = i₀
          · subst i
            have hfil : (insert x T).filter (fun e => Function.update f' x i₀ e = i₀)
                = insert x (T.filter (fun e => Function.update f' x i₀ e = i₀)) := by
              rw [Finset.filter_insert]
              simp
            have hcongr : T.filter (fun e => Function.update f' x i₀ e = i₀)
                = T.filter (fun e => f' e = i₀) := by
              apply Finset.filter_congr
              intro e he
              have hne : e ≠ x := fun h' => hx (h' ▸ he)
              rw [Function.update_of_ne hne]
            rw [hfil, hcongr, Finset.card_insert_of_notMem (by simp [hx])]
            have h2 : cap' i₀ = cap i₀ - 1 := by rw [hcap'def, Function.update_self]
            have h1 : (T.filter (fun e => f' e = i₀)).card ≤ cap i₀ - 1 := h2 ▸ hf' i₀
            omega
  5. For any color i ≠ i₀, the extended coloring f satisfies the capacity bound on T ∪ {x}.

    For i ≠ i₀, the element x is not colored i, so the fiber of i in T ∪ {x} is identical to the fiber in T under f'. Because the capacity was only modified at i₀, we have cap'(i) = cap(i), so the fiber size is bounded by cap'(i) = cap(i).

    lines 53–67

    uses Finset.filter_insert, Finset.filter_congr, Function.update_of_ne

          · have hne : i₀ ≠ i := fun h' => hii h'.symm
            have hfil : (insert x T).filter (fun e => Function.update f' x i₀ e = i)
                = T.filter (fun e => Function.update f' x i₀ e = i) := by
              rw [Finset.filter_insert]
              simp [hne]
            have hcongr : T.filter (fun e => Function.update f' x i₀ e = i)
                = T.filter (fun e => f' e = i) := by
              apply Finset.filter_congr
              intro e he
              have hne' : e ≠ x := fun h' => hx (h' ▸ he)
              rw [Function.update_of_ne hne']
            have h2 : cap' i = cap i := by
              rw [hcap'def]; exact Function.update_of_ne hii (cap i₀ - 1) cap
            rw [hfil, hcongr]
            exact h2 ▸ hf' i
  6. There exists a threshold n₀ = 2N + 2 based on a finite set of colors I whose weight sum exceeds 1, and the total edge count of K_n is C(n, 2).

    Since the infinite sum of weights ∑ a_i > 1, lemma op_258_exists_finset_sum_gt_one provides a finite subset I ⊂ ℕ+ and δ > 0 such that ∑_{i ∈ I} a_i ≥ 1 + δ. We choose an integer N ≥ |I|/δ and set n₀ = 2N + 2. For any n ≥ n₀, the complete graph on n vertices has C(n, 2) edges.

    lines 77–85

    uses op_258_exists_finset_sum_gt_one, exists_nat_ge, SimpleGraph.edgeSet_univ_card, SimpleGraph.card_edgeFinset_top_eq_card_choose_two

      classical
      obtain ⟨I, δ, hδ, hIsum⟩ := op_258_exists_finset_sum_gt_one a (fun i => (hpos i).le) hsum
      obtain ⟨N, hN⟩ := exists_nat_ge ((I.card : ℝ) / δ)
      refine ⟨2 * N + 2, ?_⟩
      intro n hn s c₀ hc₀
      have hcardE : (Finset.univ : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).card
          = n.choose 2 := by
        rw [SimpleGraph.edgeSet_univ_card, SimpleGraph.card_edgeFinset_top_eq_card_choose_two]
        simp
  7. For every n ≥ n₀, the number of selected colors |I| is at most δ * C(n, 2).

    From N ≥ |I|/δ we have |I| ≤ δ * N. Since n ≥ 2N + 2, we have C(n, 2) = n(n - 1)/2 ≥ (2N + 2)(2N + 1)/2 ≥ N. Multiplying by δ > 0 yields |I| ≤ δ * C(n, 2).

    lines 86–95

    uses div_le_iff₀, Nat.cast_choose_two

      have hIcast : (I.card : ℝ) ≤ δ * (n.choose 2 : ℝ) := by
        have h1 : (I.card : ℝ) ≤ δ * N := by
          rw [div_le_iff₀ hδ] at hN
          linarith
        have h2 : (N : ℝ) ≤ (n.choose 2 : ℝ) := by
          have hnc : ((n.choose 2 : ℕ) : ℝ) = (n : ℝ) * ((n : ℝ) - 1) / 2 := Nat.cast_choose_two ℝ n
          have hn' : (2 * (N:ℝ) + 2) ≤ (n : ℝ) := by exact_mod_cast hn
          rw [hnc]
          nlinarith
        nlinarith [hδ.le]
  8. The remaining capacity cap(i) for each color i ∈ I equals ⌊a_i * C(n, 2)⌋ - |s ∩ c₀⁻¹(i)| as real numbers.

    We define the capacity available on the uncolored edges as cap(i) = ⌊a_i * C(n, 2)⌋ - |s ∩ c₀⁻¹(i)| for i ∈ I, and 0 otherwise. Because c₀ is already a-bounded on s, we have |s ∩ c₀⁻¹(i)| ≤ a_i * C(n, 2), so the natural number subtraction does not underflow and casts directly to real subtraction.

    lines 96–106

    uses Nat.le_floor, if_pos

      set cap : ℕ+ → ℕ := fun i =>
        if i ∈ I then Nat.floor (a i * (n.choose 2 : ℝ)) - (s.filter (fun e => c₀ e = i)).card else 0
        with hcapdef
      have hcap_eq : ∀ i ∈ I, (cap i : ℝ) =
          (Nat.floor (a i * (n.choose 2 : ℝ)) : ℝ) - ((s.filter (fun e => c₀ e = i)).card : ℝ) := by
        intro i hi
        have hle : (s.filter (fun e => c₀ e = i)).card ≤ Nat.floor (a i * (n.choose 2 : ℝ)) :=
          Nat.le_floor (hc₀ i)
        simp only [hcapdef, if_pos hi]
        push_cast [hle]
        ring
  9. The total remaining capacity over I is at least the number of uncolored edges: |E(K_n) \ s| ≤ ∑_{i ∈ I} cap(i).

    The number of uncolored edges is C(n, 2) - |s|. Each floor satisfies ⌊a_i * C(n, 2)⌋ ≥ a_i * C(n, 2) - 1, so summing over I gives at least (∑_{i ∈ I} a_i) * C(n, 2) - |I| ≥ (1 + δ) * C(n, 2) - |I| ≥ C(n, 2), using |I| ≤ δ * C(n, 2). Subtracting the sum of the disjoint fibers ∑_{i ∈ I} |s ∩ c₀⁻¹(i)| ≤ |s| shows that ∑_{i ∈ I} cap(i) ≥ C(n, 2) - |s| = |E(K_n) \ s|.

    lines 107–154

    uses Finset.card_sdiff, Finset.inter_univ, Finset.card_le_univ, Nat.cast_sub, Nat.lt_floor_add_one, Finset.sum_sub_distrib, Finset.sum_mul, mul_le_mul_of_nonneg_right, Nat.cast_nonneg, Finset.sum_le_sum, Finset.disjoint_left, Finset.card_biUnion, Finset.card_le_card, Finset.biUnion_subset, Finset.filter_subset, Finset.sum_congr

      have hsum_card : (Finset.univ \ s).card ≤ ∑ i ∈ I, cap i := by
        have hR : ((Finset.univ \ s).card : ℝ) ≤ ((∑ i ∈ I, cap i : ℕ) : ℝ) := by
          have hs_card : ((Finset.univ \ s).card : ℝ) = (n.choose 2 : ℝ) - (s.card : ℝ) := by
            have h1 : (Finset.univ \ s : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).card
                = n.choose 2 - s.card := by
              rw [Finset.card_sdiff, Finset.inter_univ, hcardE]
            rw [h1]
            have h2 : s.card ≤ n.choose 2 := by rw [← hcardE]; exact Finset.card_le_univ s
            rw [Nat.cast_sub h2]
          have hfloor_lb : (∑ i ∈ I, (Nat.floor (a i * (n.choose 2 : ℝ)) : ℝ))
              ≥ (1 + δ) * (n.choose 2 : ℝ) - (I.card : ℝ) := by
            have h1 : ∀ i ∈ I, (Nat.floor (a i * (n.choose 2 : ℝ)) : ℝ)
                ≥ a i * (n.choose 2 : ℝ) - 1 := by
              intro i _
              have h3 := Nat.lt_floor_add_one (a i * (n.choose 2 : ℝ))
              linarith
            have h2 : (∑ i ∈ I, (a i * (n.choose 2 : ℝ) - 1))
                = (∑ i ∈ I, a i) * (n.choose 2 : ℝ) - (I.card : ℝ) := by
              rw [Finset.sum_sub_distrib, ← Finset.sum_mul]
              simp
            have h3 : (1 + δ) * (n.choose 2 : ℝ) ≤ (∑ i ∈ I, a i) * (n.choose 2 : ℝ) := by
              apply mul_le_mul_of_nonneg_right hIsum (Nat.cast_nonneg _)
            calc (∑ i ∈ I, (Nat.floor (a i * (n.choose 2 : ℝ)) : ℝ))
                ≥ ∑ i ∈ I, (a i * (n.choose 2 : ℝ) - 1) := Finset.sum_le_sum h1
              _ = (∑ i ∈ I, a i) * (n.choose 2 : ℝ) - (I.card : ℝ) := h2
              _ ≥ (1 + δ) * (n.choose 2 : ℝ) - (I.card : ℝ) := by linarith
          have hsi_le : (∑ i ∈ I, ((s.filter (fun e => c₀ e = i)).card : ℝ)) ≤ (s.card : ℝ) := by
            have hnat : ∑ i ∈ I, (s.filter (fun e => c₀ e = i)).card ≤ s.card := by
              have hpb : (↑I : Set ℕ+).PairwiseDisjoint (fun i => s.filter (fun e => c₀ e = i)) := by
                intro i _ j _ hij
                refine Finset.disjoint_left.mpr ?_
                intro e he he'
                simp only [Finset.mem_filter] at he he'
                exact hij (by rw [← he.2, ← he'.2])
              rw [← Finset.card_biUnion hpb]
              exact Finset.card_le_card (Finset.biUnion_subset.mpr (fun i _ => Finset.filter_subset _ _))
            calc (∑ i ∈ I, ((s.filter (fun e => c₀ e = i)).card : ℝ))
                = ((∑ i ∈ I, (s.filter (fun e => c₀ e = i)).card : ℕ) : ℝ) := by push_cast; ring
              _ ≤ (s.card : ℝ) := by exact_mod_cast hnat
          have hsum_eq : ((∑ i ∈ I, cap i : ℕ) : ℝ)
              = (∑ i ∈ I, (Nat.floor (a i * (n.choose 2 : ℝ)) : ℝ))
                - (∑ i ∈ I, ((s.filter (fun e => c₀ e = i)).card : ℝ)) := by
            push_cast
            rw [← Finset.sum_sub_distrib]
            exact Finset.sum_congr rfl hcap_eq
          rw [hs_card, hsum_eq]
          nlinarith [hfloor_lb, hsi_le, hIcast]
        exact_mod_cast hR
  10. The uncolored edges can be colored by a function f respecting capacities, and the fiber of the combined coloring c splits into disjoint contributions from s and E(K_n) \ s.

    Applying the helper lemma op_258_bounded_extension_exists_coloring to T = E(K_n) \ s yields a coloring f on uncolored edges with fibers bounded by cap(i). We define c(e) to be c₀(e) on s and f(e) on E \ s. For any color i, the edges colored i partition into the disjoint union of s ∩ c₀⁻¹(i) and (E \ s) ∩ f⁻¹(i), so the total fiber size is the sum of these two cardinalities.

    lines 155–175

    uses op_258_bounded_extension_exists_coloring, Finset.disjoint_left, Finset.card_union_of_disjoint

      obtain ⟨f, hf⟩ := op_258_bounded_extension_exists_coloring I cap (Finset.univ \ s) hsum_card
      refine ⟨fun e => if e ∈ s then c₀ e else f e, ?_, ?_⟩
      · intro i
        have hsplit : (Finset.univ.filter (fun e => (if e ∈ s then c₀ e else f e) = i))
            = s.filter (fun e => c₀ e = i) ∪ (Finset.univ \ s).filter (fun e => f e = i) := by
          ext e
          by_cases he : e ∈ s <;> simp [he]
        have hcard : (Finset.univ.filter (fun e => (if e ∈ s then c₀ e else f e) = i)).card
            = (s.filter (fun e => c₀ e = i)).card
              + ((Finset.univ \ s).filter (fun e => f e = i)).card := by
          rw [hsplit]
          have hdisj : Disjoint (s.filter (fun e => c₀ e = i))
              ((Finset.univ \ s).filter (fun e => f e = i)) := by
            rw [Finset.disjoint_left]
            intro e he he'
            simp only [Finset.mem_filter] at he he'
            simp only [Finset.mem_sdiff, Finset.mem_univ, true_and] at he'
            exact he'.1 he.1
          rw [Finset.card_union_of_disjoint hdisj]
        rw [hcard]
        push_cast
  11. For any color i ∈ I, the total fiber of c has size at most a_i * C(n, 2).

    For i ∈ I, the uncolored fiber size is at most cap(i) = ⌊a_i * C(n, 2)⌋ - |s ∩ c₀⁻¹(i)|. Adding |s ∩ c₀⁻¹(i)| cancels the subtracted term, leaving at most ⌊a_i * C(n, 2)⌋ ≤ a_i * C(n, 2).

    lines 176–198

    uses if_pos, Nat.le_floor, Nat.add_le_add_left, Nat.add_sub_of_le, Nat.floor_le, mul_nonneg, Nat.cast_nonneg

        by_cases hiI : i ∈ I
        · have hcap : cap i = Nat.floor (a i * (n.choose 2 : ℝ))
              - (s.filter (fun e => c₀ e = i)).card := by simp only [hcapdef, if_pos hiI]
          have hle : (s.filter (fun e => c₀ e = i)).card ≤ Nat.floor (a i * (n.choose 2 : ℝ)) :=
            Nat.le_floor (hc₀ i)
          have hfib : ((Finset.univ \ s).filter (fun e => f e = i)).card ≤ cap i := hf i
          rw [hcap] at hfib
          have hnat : (s.filter (fun e => c₀ e = i)).card
              + ((Finset.univ \ s).filter (fun e => f e = i)).card
              ≤ Nat.floor (a i * (n.choose 2 : ℝ)) := by
            calc (s.filter (fun e => c₀ e = i)).card
                  + ((Finset.univ \ s).filter (fun e => f e = i)).card
                ≤ (s.filter (fun e => c₀ e = i)).card
                  + (Nat.floor (a i * (n.choose 2 : ℝ)) - (s.filter (fun e => c₀ e = i)).card) :=
                    Nat.add_le_add_left hfib _
              _ = Nat.floor (a i * (n.choose 2 : ℝ)) := Nat.add_sub_of_le hle
          have hnatR : ((s.filter (fun e => c₀ e = i)).card : ℝ)
              + (((Finset.univ \ s).filter (fun e => f e = i)).card : ℝ)
              ≤ (Nat.floor (a i * (n.choose 2 : ℝ)) : ℝ) := by
            exact_mod_cast hnat
          have hfloor : (Nat.floor (a i * (n.choose 2 : ℝ)) : ℝ) ≤ a i * (n.choose 2 : ℝ) :=
            Nat.floor_le (mul_nonneg (hpos i).le (Nat.cast_nonneg _))
          linarith
  12. For i ∉ I, the fiber size is bounded by a_i * C(n, 2), and c agrees with c₀ on s.

    For i ∉ I, we set cap(i) = 0, so no uncolored edges receive color i. The fiber of c is therefore simply the original fiber s ∩ c₀⁻¹(i), which is at most a_i * C(n, 2) by assumption. Finally, by definition c(e) = c₀(e) for all e ∈ s.

    lines 199–206

    uses if_neg, Nat.le_zero

        · have hcap : cap i = 0 := by simp only [hcapdef, if_neg hiI]
          have hfib : ((Finset.univ \ s).filter (fun e => f e = i)).card ≤ cap i := hf i
          rw [hcap] at hfib
          have hfib0 : ((Finset.univ \ s).filter (fun e => f e = i)).card = 0 := Nat.le_zero.mp hfib
          simp only [hfib0, Nat.cast_zero, add_zero]
          exact hc₀ i
      · intro e he
        simp [he]
Finset.induction
A property holds for all finite sets if it holds for the empty set and is preserved under adjoining a new element.
Finset.card_insert_of_notMem
Inserting an element not already in a finite set increases its cardinality by 1.
Nat.eq_zero_or_pos
Every natural number is either zero or strictly positive.
Finset.sum_eq_zero
If every term in a finite sum is zero, the sum is zero.
Finset.sdiff_singleton_eq_erase
Removing the singleton {a} from a finite set s is equal to erasing a from s.
Finset.sum_update_of_mem
The sum of a function updated at i over a finite set containing i equals the new value b plus the sum of the original function over the remaining elements.
Finset.add_sum_erase
For an element a in s, the term f(a) plus the sum over s with a erased equals the total sum over s.
Finset.filter_insert
Filtering insert(a, s) by predicate p inserts a into the filtered set if p(a) holds, and leaves it unchanged otherwise.
Finset.filter_congr
Two filters on a finite set are equal if their predicates are equivalent on every element of the set.
Function.update_of_ne
Updating a function at a point a' does not change its value at any distinct point a.
Function.update_self
Evaluating a function updated at a with value v at the point a yields v.
op_258_exists_finset_sum_gt_one
If the infinite sum of a non-negative function exceeds 1, there is a finite subset whose sum is at least 1 + δ for some positive δ.
exists_nat_ge
In an Archimedean ordered ring, every element is bounded above by some natural number.
SimpleGraph.edgeSet_univ_card
The cardinality of the universal finset of edges of a graph equals the cardinality of its edge finset.
SimpleGraph.card_edgeFinset_top_eq_card_choose_two
The complete graph on a finite vertex set V has C(|V|, 2) edges.
div_le_iff₀
For c > 0, b / c ≤ a if and only if b ≤ a * c.
Nat.cast_choose_two
The binomial coefficient C(a, 2) equals a * (a - 1) / 2 in a division ring.
Nat.le_floor
A natural number n is at most the floor of a if and only if n ≤ a.
if_pos
If a condition c holds, the conditional expression `if c then t else e` evaluates to t.
Finset.card_sdiff
The size of the set difference t \ s is |t| - |s ∩ t|.
Finset.inter_univ
The intersection of any finite subset with the universal finset is the subset itself.
Finset.card_le_univ
The cardinality of any finset of a finite type is at most the cardinality of the type.
Nat.cast_sub
If m ≤ n, the cast of natural subtraction n - m equals the difference of the casts.
Nat.lt_floor_add_one
Any real number a is strictly less than ⌊a⌋ + 1.
Finset.sum_sub_distrib
The sum of differences f(x) - g(x) over a finite set equals the sum of f(x) minus the sum of g(x).
Finset.sum_mul
Multiplication distributes over a finite sum from the right.
mul_le_mul_of_nonneg_right
If b ≤ c and a ≥ 0, then b * a ≤ c * a.
Nat.cast_nonneg
The cast of any natural number into an ordered ring is non-negative.
Finset.sum_le_sum
If f(i) ≤ g(i) for all i in a finite set s, then the sum of f over s is at most the sum of g over s.
Finset.disjoint_left
Two finite sets are disjoint if and only if no element of the first belongs to the second.
Finset.card_biUnion
The size of a union of pairwise disjoint finite sets is the sum of their individual sizes.
Finset.card_le_card
A subset has cardinality at most that of the superset.
Finset.biUnion_subset
A union of families indexed by s is contained in s' if and only if each family is contained in s'.
Finset.filter_subset
Filtering a finite set by a predicate produces a subset of the original set.
Finset.sum_congr
Two finite sums are equal if their index sets are equal and their summands agree on all indices.
op_258_bounded_extension_exists_coloring
Any finite set T can be colored with colors from I such that each color's fiber size is at most its capacity, provided the total capacity is at least |T|.
Finset.card_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Nat.add_le_add_left
Adding a constant on the left preserves inequality of natural numbers.
Nat.add_sub_of_le
For natural numbers with a ≤ b, a + (b - a) = b.
Nat.floor_le
For any non-negative real number a, the floor ⌊a⌋ is at most a.
mul_nonneg
The product of two non-negative elements is non-negative.
if_neg
If a condition c is false, the conditional expression `if c then t else e` evaluates to e.
Nat.le_zero
A natural number is at most zero if and only if it equals zero.

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

lemma op_258_bounded_extension_exists_coloring {V : Type*} [Fintype V] [DecidableEq V]    (I : Finset ℕ+) : ∀ (cap : ℕ+ → ℕ) (T : Finset V),    T.card ≤ ∑ i ∈ I, cap i →    ∃ f : V → ℕ+, ∀ i : ℕ+, (T.filter (fun e => f e = i)).card ≤ cap i := by  classical  intro cap T  induction T using Finset.induction generalizing cap with  | empty =>      intro _      exact ⟨fun _ => 1, fun i => by simp⟩  | insert x T hx ih =>      intro h      have hpos : 0 < ∑ i ∈ I, cap i := by        have hc : (insert x T).card = T.card + 1 := Finset.card_insert_of_notMem hx        omega      have hex : ∃ i ∈ I, 0 < cap i := by        by_contra hcon        have hz : ∀ i ∈ I, cap i = 0 := by          intro i hi          rcases Nat.eq_zero_or_pos (cap i) with h' | h'          · exact h'          · exact absurd ⟨i, hi, h'⟩ hcon        have : ∑ i ∈ I, cap i = 0 := Finset.sum_eq_zero hz        omega      obtain ⟨i₀, hi₀mem, hi₀pos⟩ := hex      set cap' : ℕ+ → ℕ := Function.update cap i₀ (cap i₀ - 1) with hcap'def      have hsum' : T.card ≤ ∑ i ∈ I, cap' i := by        have hsub : I \ {i₀} = I.erase i₀ := Finset.sdiff_singleton_eq_erase i₀ I        rw [hcap'def, Finset.sum_update_of_mem hi₀mem, hsub]        have hkey : cap i₀ + ∑ x ∈ I.erase i₀, cap x = ∑ x ∈ I, cap x :=          Finset.add_sum_erase I cap hi₀mem        have hc : (insert x T).card = T.card + 1 := Finset.card_insert_of_notMem hx        omega      obtain ⟨f', hf'⟩ := ih cap' hsum'      refine ⟨Function.update f' x i₀, ?_⟩      intro i      by_cases hii : i = i₀      · subst i        have hfil : (insert x T).filter (fun e => Function.update f' x i₀ e = i₀)            = insert x (T.filter (fun e => Function.update f' x i₀ e = i₀)) := by          rw [Finset.filter_insert]          simp        have hcongr : T.filter (fun e => Function.update f' x i₀ e = i₀)            = T.filter (fun e => f' e = i₀) := by          apply Finset.filter_congr          intro e he          have hne : e ≠ x := fun h' => hx (h' ▸ he)          rw [Function.update_of_ne hne]        rw [hfil, hcongr, Finset.card_insert_of_notMem (by simp [hx])]        have h2 : cap' i₀ = cap i₀ - 1 := by rw [hcap'def, Function.update_self]        have h1 : (T.filter (fun e => f' e = i₀)).card ≤ cap i₀ - 1 := h2 ▸ hf' i₀        omega      · have hne : i₀ ≠ i := fun h' => hii h'.symm        have hfil : (insert x T).filter (fun e => Function.update f' x i₀ e = i)            = T.filter (fun e => Function.update f' x i₀ e = i) := by          rw [Finset.filter_insert]          simp [hne]        have hcongr : T.filter (fun e => Function.update f' x i₀ e = i)            = T.filter (fun e => f' e = i) := by          apply Finset.filter_congr          intro e he          have hne' : e ≠ x := fun h' => hx (h' ▸ he)          rw [Function.update_of_ne hne']        have h2 : cap' i = cap i := by          rw [hcap'def]; exact Function.update_of_ne hii (cap i₀ - 1) cap        rw [hfil, hcongr]        exact h2 ▸ hf' i/-- Partial a-bounded colourings of K_n extend to full a-bounded colourings for all large n. -/theorem op_258_bounded_extension (a : ℕ+ → ℝ) (hpos : ∀ i, 0 < a i) (hanti : Antitone a)    (hsum : 1 < ∑' i : ℕ+, ENNReal.ofReal (a i)) :    ∃ n₀ : ℕ, ∀ n ≥ n₀, ∀ (s : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet)      (c₀ : (SimpleGraph.completeGraph (Fin n)).edgeSet → ℕ+),      (∀ i : ℕ+, ((s.filter (fun e => c₀ e = i)).card : ℝ) ≤ a i * (n.choose 2 : ℝ)) →      ∃ c : (SimpleGraph.completeGraph (Fin n)).edgeSet → ℕ+,        op_258_bounded a n c ∧ ∀ e ∈ s, c e = c₀ e := by  classical  obtain ⟨I, δ, hδ, hIsum⟩ := op_258_exists_finset_sum_gt_one a (fun i => (hpos i).le) hsum  obtain ⟨N, hN⟩ := exists_nat_ge ((I.card : ℝ) / δ)  refine ⟨2 * N + 2, ?_⟩  intro n hn s c₀ hc₀  have hcardE : (Finset.univ : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).card      = n.choose 2 := by    rw [SimpleGraph.edgeSet_univ_card, SimpleGraph.card_edgeFinset_top_eq_card_choose_two]    simp  have hIcast : (I.card : ℝ) ≤ δ * (n.choose 2 : ℝ) := by    have h1 : (I.card : ℝ) ≤ δ * N := by      rw [div_le_iff₀ hδ] at hN      linarith    have h2 : (N : ℝ) ≤ (n.choose 2 : ℝ) := by      have hnc : ((n.choose 2 : ℕ) : ℝ) = (n : ℝ) * ((n : ℝ) - 1) / 2 := Nat.cast_choose_two ℝ n      have hn' : (2 * (N:ℝ) + 2) ≤ (n : ℝ) := by exact_mod_cast hn      rw [hnc]      nlinarith    nlinarith [hδ.le]  set cap : ℕ+ → ℕ := fun i =>    if i ∈ I then Nat.floor (a i * (n.choose 2 : ℝ)) - (s.filter (fun e => c₀ e = i)).card else 0    with hcapdef  have hcap_eq : ∀ i ∈ I, (cap i : ℝ) =      (Nat.floor (a i * (n.choose 2 : ℝ)) : ℝ) - ((s.filter (fun e => c₀ e = i)).card : ℝ) := by    intro i hi    have hle : (s.filter (fun e => c₀ e = i)).card ≤ Nat.floor (a i * (n.choose 2 : ℝ)) :=      Nat.le_floor (hc₀ i)    simp only [hcapdef, if_pos hi]    push_cast [hle]    ring  have hsum_card : (Finset.univ \ s).card ≤ ∑ i ∈ I, cap i := by    have hR : ((Finset.univ \ s).card : ℝ) ≤ ((∑ i ∈ I, cap i : ℕ) : ℝ) := by      have hs_card : ((Finset.univ \ s).card : ℝ) = (n.choose 2 : ℝ) - (s.card : ℝ) := by        have h1 : (Finset.univ \ s : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).card            = n.choose 2 - s.card := by          rw [Finset.card_sdiff, Finset.inter_univ, hcardE]        rw [h1]        have h2 : s.card ≤ n.choose 2 := by rw [← hcardE]; exact Finset.card_le_univ s        rw [Nat.cast_sub h2]      have hfloor_lb : (∑ i ∈ I, (Nat.floor (a i * (n.choose 2 : ℝ)) : ℝ))          ≥ (1 + δ) * (n.choose 2 : ℝ) - (I.card : ℝ) := by        have h1 : ∀ i ∈ I, (Nat.floor (a i * (n.choose 2 : ℝ)) : ℝ)            ≥ a i * (n.choose 2 : ℝ) - 1 := by          intro i _          have h3 := Nat.lt_floor_add_one (a i * (n.choose 2 : ℝ))          linarith        have h2 : (∑ i ∈ I, (a i * (n.choose 2 : ℝ) - 1))            = (∑ i ∈ I, a i) * (n.choose 2 : ℝ) - (I.card : ℝ) := by          rw [Finset.sum_sub_distrib, ← Finset.sum_mul]          simp        have h3 : (1 + δ) * (n.choose 2 : ℝ) ≤ (∑ i ∈ I, a i) * (n.choose 2 : ℝ) := by          apply mul_le_mul_of_nonneg_right hIsum (Nat.cast_nonneg _)        calc (∑ i ∈ I, (Nat.floor (a i * (n.choose 2 : ℝ)) : ℝ))            ≥ ∑ i ∈ I, (a i * (n.choose 2 : ℝ) - 1) := Finset.sum_le_sum h1          _ = (∑ i ∈ I, a i) * (n.choose 2 : ℝ) - (I.card : ℝ) := h2          _ ≥ (1 + δ) * (n.choose 2 : ℝ) - (I.card : ℝ) := by linarith      have hsi_le : (∑ i ∈ I, ((s.filter (fun e => c₀ e = i)).card : ℝ)) ≤ (s.card : ℝ) := by        have hnat : ∑ i ∈ I, (s.filter (fun e => c₀ e = i)).card ≤ s.card := by          have hpb : (↑I : Set ℕ+).PairwiseDisjoint (fun i => s.filter (fun e => c₀ e = i)) := by            intro i _ j _ hij            refine Finset.disjoint_left.mpr ?_            intro e he he'            simp only [Finset.mem_filter] at he he'            exact hij (by rw [← he.2, ← he'.2])          rw [← Finset.card_biUnion hpb]          exact Finset.card_le_card (Finset.biUnion_subset.mpr (fun i _ => Finset.filter_subset _ _))        calc (∑ i ∈ I, ((s.filter (fun e => c₀ e = i)).card : ℝ))            = ((∑ i ∈ I, (s.filter (fun e => c₀ e = i)).card : ℕ) : ℝ) := by push_cast; ring          _ ≤ (s.card : ℝ) := by exact_mod_cast hnat      have hsum_eq : ((∑ i ∈ I, cap i : ℕ) : ℝ)          = (∑ i ∈ I, (Nat.floor (a i * (n.choose 2 : ℝ)) : ℝ))            - (∑ i ∈ I, ((s.filter (fun e => c₀ e = i)).card : ℝ)) := by        push_cast        rw [← Finset.sum_sub_distrib]        exact Finset.sum_congr rfl hcap_eq      rw [hs_card, hsum_eq]      nlinarith [hfloor_lb, hsi_le, hIcast]    exact_mod_cast hR  obtain ⟨f, hf⟩ := op_258_bounded_extension_exists_coloring I cap (Finset.univ \ s) hsum_card  refine ⟨fun e => if e ∈ s then c₀ e else f e, ?_, ?_⟩  · intro i    have hsplit : (Finset.univ.filter (fun e => (if e ∈ s then c₀ e else f e) = i))        = s.filter (fun e => c₀ e = i) ∪ (Finset.univ \ s).filter (fun e => f e = i) := by      ext e      by_cases he : e ∈ s <;> simp [he]    have hcard : (Finset.univ.filter (fun e => (if e ∈ s then c₀ e else f e) = i)).card        = (s.filter (fun e => c₀ e = i)).card          + ((Finset.univ \ s).filter (fun e => f e = i)).card := by      rw [hsplit]      have hdisj : Disjoint (s.filter (fun e => c₀ e = i))          ((Finset.univ \ s).filter (fun e => f e = i)) := by        rw [Finset.disjoint_left]        intro e he he'        simp only [Finset.mem_filter] at he he'        simp only [Finset.mem_sdiff, Finset.mem_univ, true_and] at he'        exact he'.1 he.1      rw [Finset.card_union_of_disjoint hdisj]    rw [hcard]    push_cast    by_cases hiI : i ∈ I    · have hcap : cap i = Nat.floor (a i * (n.choose 2 : ℝ))          - (s.filter (fun e => c₀ e = i)).card := by simp only [hcapdef, if_pos hiI]      have hle : (s.filter (fun e => c₀ e = i)).card ≤ Nat.floor (a i * (n.choose 2 : ℝ)) :=        Nat.le_floor (hc₀ i)      have hfib : ((Finset.univ \ s).filter (fun e => f e = i)).card ≤ cap i := hf i      rw [hcap] at hfib      have hnat : (s.filter (fun e => c₀ e = i)).card          + ((Finset.univ \ s).filter (fun e => f e = i)).card          ≤ Nat.floor (a i * (n.choose 2 : ℝ)) := by        calc (s.filter (fun e => c₀ e = i)).card              + ((Finset.univ \ s).filter (fun e => f e = i)).card            ≤ (s.filter (fun e => c₀ e = i)).card              + (Nat.floor (a i * (n.choose 2 : ℝ)) - (s.filter (fun e => c₀ e = i)).card) :=                Nat.add_le_add_left hfib _          _ = Nat.floor (a i * (n.choose 2 : ℝ)) := Nat.add_sub_of_le hle      have hnatR : ((s.filter (fun e => c₀ e = i)).card : ℝ)          + (((Finset.univ \ s).filter (fun e => f e = i)).card : ℝ)          ≤ (Nat.floor (a i * (n.choose 2 : ℝ)) : ℝ) := by        exact_mod_cast hnat      have hfloor : (Nat.floor (a i * (n.choose 2 : ℝ)) : ℝ) ≤ a i * (n.choose 2 : ℝ) :=        Nat.floor_le (mul_nonneg (hpos i).le (Nat.cast_nonneg _))      linarith    · have hcap : cap i = 0 := by simp only [hcapdef, if_neg hiI]      have hfib : ((Finset.univ \ s).filter (fun e => f e = i)).card ≤ cap i := hf i      rw [hcap] at hfib      have hfib0 : ((Finset.univ \ s).filter (fun e => f e = i)).card = 0 := Nat.le_zero.mp hfib      simp only [hfib0, Nat.cast_zero, add_zero]      exact hc₀ i  · intro e he    simp [he]
See it in the graphDiscuss this resultChallenge it