op_258_bounded_extension
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
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- Used by 1
- op_258_forces_of_forces_smul_blowupFor γ ≥ 1 and k ≥ 1: if a forces a monochromatic K_{γk}, then the profile γ·a forces a monochromatic K_k.
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.
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).
uses
Finset.inductionclassical intro cap T induction T using Finset.induction generalizing cap with | empty => intro _ exact ⟨fun _ => 1, fun i => by simp⟩
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.
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⟩ := hexDecreasing 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.
uses
Finset.sdiff_singleton_eq_erase,Finset.sum_update_of_mem,Finset.add_sum_erase,Finset.card_insert_of_notMemset 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'
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₀).
uses
Finset.filter_insert,Finset.filter_congr,Function.update_of_ne,Finset.card_insert_of_notMem,Function.update_selfrefine ⟨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
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).
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
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.
uses
op_258_exists_finset_sum_gt_one,exists_nat_ge,SimpleGraph.edgeSet_univ_card,SimpleGraph.card_edgeFinset_top_eq_card_choose_twoclassical 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
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).
uses
div_le_iff₀,Nat.cast_choose_twohave 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]
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.
uses
Nat.le_floor,if_posset 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
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|.
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_congrhave 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
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.
uses
op_258_bounded_extension_exists_coloring,Finset.disjoint_left,Finset.card_union_of_disjointobtain ⟨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
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).
uses
if_pos,Nat.le_floor,Nat.add_le_add_left,Nat.add_sub_of_le,Nat.floor_le,mul_nonneg,Nat.cast_nonnegby_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
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.
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.
- The file proves an auxiliary lemma (`op_258_bounded_extension_exists_coloring`) showing that any finite set T can be colored with bounded fiber sizes whenever the sum of capacities is at least |T|.
- The threshold n₀ = 2N + 2 is chosen so that C(n, 2) ≥ N ≥ |I|/δ, ensuring that the aggregate floor rounding loss |I| across colors is strictly absorbed by the surplus δ * C(n, 2).
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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]