op_258_forces_of_capacity_lt_one
If k ≥ 2 and Σ_i min(a_i, 1 - 1/(k-1)) < 1, then every a-bounded colouring of K_n for large n already contains a monochromatic K_k; i.e. a forces a monochromatic K_k.
Statement
theorem op_258_forces_of_capacity_lt_one (a : ℕ+ → ℝ) (k : ℕ) (hk : 2 ≤ k)
(hcap : (∑' i : ℕ+, ENNReal.ofReal (min (a i) (1 - 1 / ((k : ℝ) - 1)))) < 1) :
op_258_forces a k- Source
- step towards op_258_forces_step
- Verified
- 21 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- op_258_mono_clique_of_fiber_gt_turanIf a single colour class of an edge colouring of K_n has strictly more edges than the Turán bound for K_{r+1}-free graphs (r ≥ 1), then…
- op_258_card_fiber_sumFor any colouring c of the edges of the complete graph on Fin n, the sum over the colours actually used of the number of edges of that…
- op_258_forces_twoFor every decay profile a, a forces a monochromatic K_2.
- op_258_forcesThe decay profile a forces a monochromatic K_k if for all sufficiently large n, every a-bounded colouring of the edges of K_n has a…
- 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 *…
- op_258_has_mono_cliqueThe colouring c of the edges of K_n has a monochromatic K_k: there are a k-element vertex set s and a colour i such that every edge inside…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
The proof, explained
The proof proceeds by contradiction. For k = 2 the result is trivial; for k ≥ 3, any k-clique-free colouring of K_n must obey Turán's theorem, which caps the size of every color class at roughly (1 - 1/(k - 1)) choose(n, 2) + n. Since the capped profile sum S is strictly less than 1 by deficit ε = 1 - S > 0, at most two colors can exceed the threshold θ = 1 - 1/(k - 1), contributing at most 2n surplus edges beyond S choose(n, 2). For large n, this linear surplus 2n cannot compensate for the quadratic deficit ε choose(n, 2), showing that no such colouring can exist.
The edge count of the Turán graph T(n, r) is at most (1 - 1/r) n² / 2.
The expression ((n² - (n % r)²)(r - 1)) / (2r) + choose(n % r, 2) is the exact number of edges of the Turán graph T(n, r). By the Turán graph edge bound SimpleGraph.mul_card_edgeFinset_turanGraph_le, 2r |E(T(n, r))| ≤ (r - 1)n². Dividing by 2r on both sides gives |E(T(n, r))| ≤ ((r - 1) / (2r)) n² = (1 - 1/r) n² / 2.
uses
SimpleGraph.card_edgeFinset_turanGraph.symm,SimpleGraph.mul_card_edgeFinset_turanGraph_le,le_div_iff₀have h1 : (n ^ 2 - (n % r) ^ 2) * (r - 1) / (2 * r) + (n % r).choose 2 = (SimpleGraph.turanGraph n r).edgeFinset.card := SimpleGraph.card_edgeFinset_turanGraph.symm rw [h1] have h2 := SimpleGraph.mul_card_edgeFinset_turanGraph_le (n := n) (r := r) have hr_pos : (0 : ℝ) < (r : ℝ) := Nat.cast_pos.mpr hr have h2_real : 2 * (r : ℝ) * ((SimpleGraph.turanGraph n r).edgeFinset.card : ℝ) ≤ ((r - 1 : ℕ) : ℝ) * (n ^ 2 : ℝ) := by exact_mod_cast h2 have hr_sub : ((r - 1 : ℕ) : ℝ) = (r : ℝ) - 1 := by push_cast [hr]; rfl rw [hr_sub] at h2_real have hdiv : ((SimpleGraph.turanGraph n r).edgeFinset.card : ℝ) ≤ ((r : ℝ) - 1) * (n ^ 2 : ℝ) / (2 * (r : ℝ)) := by exact (le_div_iff₀ (by positivity)).mpr (by linarith) have heq : ((r : ℝ) - 1) * (n ^ 2 : ℝ) / (2 * (r : ℝ)) = (1 - 1 / (r : ℝ)) * (n ^ 2 : ℝ) / 2 := by have : (r : ℝ) ≠ 0 := by positivity field_simp have h_mid : ((SimpleGraph.turanGraph n r).edgeFinset.card : ℝ) ≤ (1 - 1 / (r : ℝ)) * (n ^ 2 : ℝ) / 2 := by rwa [← heq]
The edge count of T(n, r) is at most (1 - 1/r) choose(n, 2) + n.
Using choose(n, 2) = n(n - 1) / 2, the term (1 - 1/r) n² / 2 expands as (1 - 1/r) choose(n, 2) + (1 - 1/r) n / 2. Since r ≥ 1, we have 1 - 1/r ≤ 1, so the remainder (1 - 1/r) n / 2 is at most n / 2 ≤ n. Adding this yields the desired upper bound.
uses
Nat.cast_choose_two,div_le_iff₀,div_poshave hch : (n.choose 2 : ℝ) = (n : ℝ) * ((n : ℝ) - 1) / 2 := Nat.cast_choose_two ℝ n have h_sq : (1 - 1 / (r : ℝ)) * (n ^ 2 : ℝ) / 2 = (1 - 1 / (r : ℝ)) * (n.choose 2 : ℝ) + (1 - 1 / (r : ℝ)) * (n : ℝ) / 2 := by rw [hch] ring rw [h_sq] at h_mid have hr_le : (1 : ℝ) / (r : ℝ) ≤ 1 := by rw [div_le_iff₀ hr_pos] have : (1 : ℝ) ≤ (r : ℝ) := by exact_mod_cast hr linarith have : (1 - 1 / (r : ℝ)) * (n : ℝ) / 2 ≤ (n : ℝ) := by have h_nonneg : (n : ℝ) ≥ 0 := by positivity have : 1 - 1 / (r : ℝ) ≤ 1 := by have : 0 < (1 : ℝ) / (r : ℝ) := div_pos (by norm_num) hr_pos linarith nlinarith linarith
If k ≥ 3 and |J|(1 - 1/(k - 1)) ≤ 1, then |J| ≤ 2.
Since k ≥ 3, we have k - 1 ≥ 2, so 1 / (k - 1) ≤ 1/2, which implies 1 - 1/(k - 1) ≥ 1/2. Therefore |J| * (1/2) ≤ |J|(1 - 1/(k - 1)) ≤ 1, which implies |J| ≤ 2.
uses
div_le_div_iff₀have hk_sub : (2 : ℝ) ≤ (k : ℝ) - 1 := by have : (3 : ℝ) ≤ (k : ℝ) := by exact_mod_cast hk linarith have htheta : (1 / 2 : ℝ) ≤ 1 - 1 / ((k : ℝ) - 1) := by have : 1 / ((k : ℝ) - 1) ≤ 1 / 2 := by rw [div_le_div_iff₀ (by positivity) (by norm_num)] linarith linarith have : (J_card : ℝ) * (1 / 2) ≤ (J_card : ℝ) * (1 - 1 / ((k : ℝ) - 1)) := by have : 0 ≤ (J_card : ℝ) := by positivity nlinarith linarith
The theorem holds in the base case k = 2.
We split on whether k = 2 or k ≥ 3. In the case k = 2, every edge is a monochromatic K₂, so op_258_forces_two immediately proves the claim.
uses
eq_or_lt_of_le,op_258_forces_tworcases eq_or_lt_of_le hk with rfl | hk3 · exact op_258_forces_two a
For k ≥ 3, the threshold θ = 1 - 1/(k - 1) is at least 1/2, and the deficit ε = 1 - S is positive.
When k ≥ 3, k - 1 ≥ 2, so θ = 1 - 1/(k - 1) ≥ 1/2 > 0. The capacity hypothesis says that the series S = ∑_i min(a_i, θ) is strictly less than 1 in ENNReal. Thus S is finite and its real value satisfies S.toReal < 1, leaving a positive deficit ε = 1 - S.toReal > 0.
uses
div_le_div_iff₀,ne_of_lt,le_top,ENNReal.toReal_lt_toReal· set θ : ℝ := 1 - 1 / ((k : ℝ) - 1) have hk_sub : (2 : ℝ) ≤ (k : ℝ) - 1 := by have : (3 : ℝ) ≤ (k : ℝ) := by exact_mod_cast hk3 linarith have hθ_ge : (1 / 2 : ℝ) ≤ θ := by have : 1 / ((k : ℝ) - 1) ≤ 1 / 2 := by rw [div_le_div_iff₀ (by positivity) (by norm_num)] linarith linarith have hθ_pos : 0 < θ := by linarith set S : ENNReal := ∑' i : ℕ+, ENNReal.ofReal (min (a i) θ) have hne : S ≠ ⊤ := ne_of_lt (hcap.trans_le le_top) have hS_lt : S.toReal < 1 := by have h_lt := (ENNReal.toReal_lt_toReal hne (by norm_num)).mpr hcap simpa using h_lt set ε : ℝ := 1 - S.toReal have hε : 0 < ε := by linarith
Choose n₀ > 4/ε + 5; any counterexample on K_n with n ≥ n₀ has n ≥ 2 and choose(n, 2) > 0.
We choose n₀ > 4/ε + 5 by Archimedean property. For any n ≥ n₀ and any a-bounded colouring c of K_n, suppose for contradiction that c contains no monochromatic K_k. Since n > 5, we have n ≥ 2, so the edge set of K_n is non-empty with choose(n, 2) > 0.
uses
exists_nat_gt,div_pos,Nat.choose_posobtain ⟨n₀, hn₀⟩ := exists_nat_gt (4 / ε + 5) use n₀ intro n hn c hc by_contra h_no have hn_pos : 0 < (n : ℝ) := by have : 0 < 4 / ε + 5 := by positivity have : 4 / ε + 5 < (n : ℝ) := hn₀.trans_le (by exact_mod_cast hn) linarith have hn2 : 2 ≤ n := by have : (2 : ℝ) ≤ (n : ℝ) := by have : 0 < 4 / ε := div_pos (by norm_num) hε have : 4 / ε + 5 < (n : ℝ) := hn₀.trans_le (by exact_mod_cast hn) linarith exact_mod_cast this have hpos : 0 < (n.choose 2 : ℝ) := by have : 0 < n.choose 2 := Nat.choose_pos hn2 exact_mod_cast this
Each color class has size at most θ choose(n, 2) + n.
Let r = k - 1 ≥ 1. If any color class had more edges than the Turán graph T(n, r), Turán's theorem op_258_mono_clique_of_fiber_gt_turan would produce a monochromatic K_{r+1} = K_k, contradicting the absence of monochromatic K_k. Combining this with the Turán bound lemma op_258_forces_of_capacity_lt_one_turan_bound_le gives an upper bound of θ choose(n, 2) + n for each color class.
uses
Nat.cast_sub,op_258_mono_clique_of_fiber_gt_turan,op_258_forces_of_capacity_lt_one_turan_bound_leset r := k - 1 have hr : 1 ≤ r := by omega have hr_add : r + 1 = k := by omega have hr_cast : (r : ℝ) = (k : ℝ) - 1 := by simpa using Nat.cast_sub (R := ℝ) (by omega : 1 ≤ k) have h_turan_i : ∀ i : ℕ+, (((Finset.univ : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).filter (fun e => c e = i)).card : ℝ) ≤ θ * (n.choose 2 : ℝ) + n := by intro i have h_not_gt : ¬ ((Finset.univ.filter (fun e => c e = i)).card > (n ^ 2 - (n % r) ^ 2) * (r - 1) / (2 * r) + (n % r).choose 2) := by intro h_gt have h_mono := op_258_mono_clique_of_fiber_gt_turan n r hr c i h_gt rw [hr_add] at h_mono exact h_no h_mono have h_le_turan : ((Finset.univ.filter (fun e => c e = i)).card : ℝ) ≤ (((n ^ 2 - (n % r) ^ 2) * (r - 1) / (2 * r) + (n % r).choose 2 : ℕ) : ℝ) := by have : (Finset.univ.filter (fun e => c e = i)).card ≤ (n ^ 2 - (n % r) ^ 2) * (r - 1) / (2 * r) + (n % r).choose 2 := by omega exact_mod_cast this have hturan := op_258_forces_of_capacity_lt_one_turan_bound_le n r hr rw [hr_cast] at hturan exact h_le_turan.trans hturan
The set J of heavy colors (with a_i > θ) satisfies |J| ≤ 2, so |J|n ≤ 2n.
Let U be the set of colors appearing on the edges of K_n. Every color in U has at least one edge, so a_i ≥ 0, which implies min(a_i, θ) ≥ 0. The sum of min(a_i, θ) over U is at most the total sum S. On the subset J where a_i > θ, min(a_i, θ) = θ, so |J|θ ≤ S.toReal < 1. By the lemma op_258_forces_of_capacity_lt_one_card_le_two, this implies |J| ≤ 2, and therefore |J|n ≤ 2n.
uses
nonneg_of_mul_nonneg_left,le_min,le_of_lt,ENNReal.sum_le_tsum,ne_of_lt,le_top,ENNReal.toReal_le_toReal,ENNReal.ofReal_sum_of_nonneg,ENNReal.toReal_ofReal,Finset.sum_nonneg,Finset.filter_subset,Finset.sum_le_sum_of_subset_of_nonneg,min_eq_right,Finset.sum_congr,Finset.sum_const,nsmul_eq_mul,op_258_forces_of_capacity_lt_one_card_le_twoset U := Finset.univ.image c set J := U.filter (fun i => θ < a i) have ha_nonneg : ∀ i ∈ U, 0 ≤ a i := by intro i hi rcases Finset.mem_image.mp hi with ⟨e, -, he⟩ have hmem : e ∈ (Finset.univ : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).filter (fun e' => c e' = i) := by simp [he] have hcard : 1 ≤ ((Finset.univ : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).filter (fun e' => c e' = i)).card := Finset.card_pos.mpr ⟨e, hmem⟩ have hcard_real : (1 : ℝ) ≤ (((Finset.univ : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).filter (fun e' => c e' = i)).card : ℝ) := by exact_mod_cast hcard have hle_i := hc i have : 0 < a i * (n.choose 2 : ℝ) := by linarith exact nonneg_of_mul_nonneg_left (by linarith) hpos have hmin_nonneg : ∀ i ∈ U, 0 ≤ min (a i) θ := by intro i hi exact le_min (ha_nonneg i hi) (le_of_lt hθ_pos) have h1 : ∑ i ∈ U, ENNReal.ofReal (min (a i) θ) ≤ S := ENNReal.sum_le_tsum U have hne1 : (∑ i ∈ U, ENNReal.ofReal (min (a i) θ)) ≠ ⊤ := ne_of_lt (h1.trans_lt (hcap.trans_le le_top)) have h_sum_le := (ENNReal.toReal_le_toReal hne1 hne).mpr h1 rw [← ENNReal.ofReal_sum_of_nonneg hmin_nonneg] at h_sum_le rw [ENNReal.toReal_ofReal (Finset.sum_nonneg hmin_nonneg)] at h_sum_le have hJ_sub : J ⊆ U := Finset.filter_subset _ _ have h_subsum : (∑ i ∈ J, min (a i) θ) ≤ ∑ i ∈ U, min (a i) θ := Finset.sum_le_sum_of_subset_of_nonneg hJ_sub (fun i hi _ => hmin_nonneg i hi) have hJ_eq : ∀ i ∈ J, min (a i) θ = θ := by intro i hi have : θ < a i := (Finset.mem_filter.mp hi).2 exact min_eq_right (le_of_lt this) have hJ_sum : (∑ i ∈ J, min (a i) θ) = (J.card : ℝ) * θ := by rw [Finset.sum_congr rfl hJ_eq, Finset.sum_const, nsmul_eq_mul] have hJ_le_S : (J.card : ℝ) * θ ≤ S.toReal := by linarith have hJ_le_two : (J.card : ℝ) ≤ 2 := op_258_forces_of_capacity_lt_one_card_le_two k hk3 J.card (by linarith) have hJ_mul_le : (J.card : ℝ) * (n : ℝ) ≤ 2 * (n : ℝ) := by nlinarith
The sum of all color class sizes is at most (∑_{i ∈ U} min(a_i, θ)) choose(n, 2) + |J|n.
We partition the colors in U into J and U \ J. For each color i ∈ J, its size is at most min(a_i, θ) choose(n, 2) + n by the Turán bound. For each color i ∉ J, we have a_i ≤ θ, so min(a_i, θ) = a_i, and by the profile bound its size is at most a_i choose(n, 2) = min(a_i, θ) choose(n, 2). Summing over U gives the inequality.
uses
min_eq_left,Finset.sum_filter_add_sum_filter_not,add_mul,Finset.sum_le_sum,Finset.sum_add_distrib,Finset.sum_const,nsmul_eq_mul,Finset.sum_mulset fib := fun i : ℕ+ => (((Finset.univ : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).filter (fun e => c e = i)).card : ℝ) have hJ_fib : ∀ i ∈ J, fib i ≤ min (a i) θ * (n.choose 2 : ℝ) + n := by intro i hi rw [hJ_eq i hi] exact h_turan_i i have hnotJ_fib : ∀ i ∈ U.filter (fun x => ¬ (θ < a x)), fib i ≤ min (a i) θ * (n.choose 2 : ℝ) := by intro i hi have hnot : ¬ (θ < a i) := (Finset.mem_filter.mp hi).2 have hle : a i ≤ θ := not_lt.mp hnot have heq : min (a i) θ = a i := min_eq_left hle rw [heq] exact hc i have h_fib_sum : ∑ i ∈ U, fib i ≤ (∑ i ∈ U, min (a i) θ) * (n.choose 2 : ℝ) + (J.card : ℝ) * (n : ℝ) := by have h1 : ∑ i ∈ U, fib i = (∑ i ∈ J, fib i) + ∑ i ∈ U.filter (fun x => ¬ (θ < a x)), fib i := (Finset.sum_filter_add_sum_filter_not U (fun x => θ < a x) fib).symm have h2 : ∑ i ∈ U, min (a i) θ = (∑ i ∈ J, min (a i) θ) + ∑ i ∈ U.filter (fun x => ¬ (θ < a x)), min (a i) θ := (Finset.sum_filter_add_sum_filter_not U (fun x => θ < a x) (fun i => min (a i) θ)).symm rw [h1, h2, add_mul] have s1 : ∑ i ∈ J, fib i ≤ ∑ i ∈ J, (min (a i) θ * (n.choose 2 : ℝ) + n) := Finset.sum_le_sum hJ_fib have s2 : ∑ i ∈ U.filter (fun x => ¬ (θ < a x)), fib i ≤ ∑ i ∈ U.filter (fun x => ¬ (θ < a x)), (min (a i) θ * (n.choose 2 : ℝ)) := Finset.sum_le_sum hnotJ_fib rw [Finset.sum_add_distrib, Finset.sum_const, nsmul_eq_mul] at s1 rw [← Finset.sum_mul] at s1 rw [← Finset.sum_mul] at s2 linarith have h_card_fiber : ∑ i ∈ U, fib i = (n.choose 2 : ℝ) := op_258_card_fiber_sum n c
The total edge count choose(n, 2) contradicts the upper bound, proving the theorem.
The color classes partition the choose(n, 2) edges of K_n by op_258_card_fiber_sum. Combining this with the bounds on the weight sum and |J|n gives choose(n, 2) ≤ S.toReal choose(n, 2) + 2n, which rearranges to ε choose(n, 2) ≤ 2n. Substituting choose(n, 2) = n(n - 1) / 2 and simplifying yields ε(n - 1) ≤ 4. But our choice of n ≥ n₀ > 4/ε + 5 guarantees ε(n - 1) > 4, a contradiction.
uses
op_258_card_fiber_sum,Nat.cast_choose_two,div_lt_iff₀have h_le_almost : (n.choose 2 : ℝ) ≤ S.toReal * (n.choose 2 : ℝ) + 2 * (n : ℝ) := by calc (n.choose 2 : ℝ) = ∑ i ∈ U, fib i := h_card_fiber.symm _ ≤ (∑ i ∈ U, min (a i) θ) * (n.choose 2 : ℝ) + (J.card : ℝ) * (n : ℝ) := h_fib_sum _ ≤ S.toReal * (n.choose 2 : ℝ) + 2 * (n : ℝ) := by have : (∑ i ∈ U, min (a i) θ) * (n.choose 2 : ℝ) ≤ S.toReal * (n.choose 2 : ℝ) := by nlinarith linarith have h_le_fin : ε * (n.choose 2 : ℝ) ≤ 2 * (n : ℝ) := by linarith have hch : (n.choose 2 : ℝ) = (n : ℝ) * ((n : ℝ) - 1) / 2 := Nat.cast_choose_two ℝ n rw [hch] at h_le_fin have hn_gt : 4 / ε + 5 < (n : ℝ) := hn₀.trans_le (by exact_mod_cast hn) have h4 : 4 < ε * ((n : ℝ) - 1) := by have h1 : 4 / ε < (n : ℝ) - 1 := by linarith have h2 := (div_lt_iff₀ hε).mp h1 linarith have : 2 * (n : ℝ) < ε * ((n : ℝ) * ((n : ℝ) - 1) / 2) := by have : 4 * (n : ℝ) < ε * ((n : ℝ) - 1) * (n : ℝ) := by nlinarith linarith linarith
SimpleGraph.card_edgeFinset_turanGraph.symm- The number of edges in the Turán graph T(n, r) equals ((n² - (n % r)²)(r - 1)) / (2r) + choose(n % r, 2)
SimpleGraph.mul_card_edgeFinset_turanGraph_le- The number of edges in the Turán graph T(n, r) satisfies 2r |E(T(n, r))| ≤ (r - 1)n²
le_div_iff₀- For c > 0, a ≤ b / c is equivalent to a * c ≤ b
Nat.cast_choose_two- The binomial coefficient choose(n, 2) cast to a division ring equals n(n - 1) / 2
div_le_iff₀- For c > 0, b / c ≤ a is equivalent to b ≤ a * c
div_pos- The quotient of two positive numbers is positive
div_le_div_iff₀- For b > 0 and d > 0, a / b ≤ c / d is equivalent to a * d ≤ c * b
eq_or_lt_of_le- If a ≤ b, then either a = b or a < b
op_258_forces_two- Any profile forces a monochromatic K₂
ne_of_lt- A number strictly less than another cannot equal it
le_top- Every element in a type with a top element is at most ⊤
ENNReal.toReal_lt_toReal- For non-infinite ENNReal values, a.toReal < b.toReal if and only if a < b
exists_nat_gt- For any real number, there exists a strictly greater natural number
Nat.choose_pos- If k ≤ n, then choose(n, k) is strictly positive
Nat.cast_sub- Casting n - m to an additive group with one equals n - m when m ≤ n
op_258_mono_clique_of_fiber_gt_turan- If a color class in a graph on n vertices has more edges than the Turán graph T(n, r), it contains a monochromatic K_{r+1}
op_258_forces_of_capacity_lt_one_turan_bound_le- The edge count of T(n, r) is at most (1 - 1/r) choose(n, 2) + n
nonneg_of_mul_nonneg_left- If a * b ≥ 0 and b > 0, then a ≥ 0
le_min- A number is at most min a b if it is at most both a and b
le_of_lt- If a < b then a ≤ b
ENNReal.sum_le_tsum- A finite sum of nonnegative terms is bounded by the infinite series
ENNReal.toReal_le_toReal- For non-infinite ENNReal values, a.toReal ≤ b.toReal if and only if a ≤ b
ENNReal.ofReal_sum_of_nonneg- ENNReal.ofReal distributes over finite sums of nonnegative real numbers
ENNReal.toReal_ofReal- The real value of ENNReal.ofReal r is r when r ≥ 0
Finset.sum_nonneg- A finite sum of nonnegative terms is nonnegative
Finset.filter_subset- Filtering a finset produces a subset
Finset.sum_le_sum_of_subset_of_nonneg- A sum of nonnegative terms over a subset is at most the sum over the superset
min_eq_right- If b ≤ a, then min a b = b
Finset.sum_congr- Sums of equal functions over equal sets are equal
Finset.sum_const- The sum of a constant b over a finset s equals |s| • b
nsmul_eq_mul- Scalar multiplication by a natural n equals multiplication by n cast to the ring
op_258_forces_of_capacity_lt_one_card_le_two- If k ≥ 3 and |J|(1 - 1/(k - 1)) ≤ 1, then |J| ≤ 2
min_eq_left- If a ≤ b, then min a b = a
Finset.sum_filter_add_sum_filter_not- A sum over a finset equals the sum over elements satisfying p plus the sum over elements satisfying ¬p
add_mul- Right distributivity of multiplication over addition
Finset.sum_le_sum- If f x ≤ g x for all x in s, then sum f ≤ sum g
Finset.sum_add_distrib- The sum of f + g over a finset equals the sum of f plus the sum of g
Finset.sum_mul- Factoring a constant out of a finite sum
op_258_card_fiber_sum- The sum of the sizes of the color classes in K_n equals choose(n, 2)
div_lt_iff₀- For c > 0, b / c < a is equivalent to b < a * c
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_forces_of_capacity_lt_one_turan_bound_le (n r : ℕ) (hr : 1 ≤ r) : (((n ^ 2 - (n % r) ^ 2) * (r - 1) / (2 * r) + (n % r).choose 2 : ℕ) : ℝ) ≤ (1 - 1 / (r : ℝ)) * (n.choose 2 : ℝ) + n := by have h1 : (n ^ 2 - (n % r) ^ 2) * (r - 1) / (2 * r) + (n % r).choose 2 = (SimpleGraph.turanGraph n r).edgeFinset.card := SimpleGraph.card_edgeFinset_turanGraph.symm rw [h1] have h2 := SimpleGraph.mul_card_edgeFinset_turanGraph_le (n := n) (r := r) have hr_pos : (0 : ℝ) < (r : ℝ) := Nat.cast_pos.mpr hr have h2_real : 2 * (r : ℝ) * ((SimpleGraph.turanGraph n r).edgeFinset.card : ℝ) ≤ ((r - 1 : ℕ) : ℝ) * (n ^ 2 : ℝ) := by exact_mod_cast h2 have hr_sub : ((r - 1 : ℕ) : ℝ) = (r : ℝ) - 1 := by push_cast [hr]; rfl rw [hr_sub] at h2_real have hdiv : ((SimpleGraph.turanGraph n r).edgeFinset.card : ℝ) ≤ ((r : ℝ) - 1) * (n ^ 2 : ℝ) / (2 * (r : ℝ)) := by exact (le_div_iff₀ (by positivity)).mpr (by linarith) have heq : ((r : ℝ) - 1) * (n ^ 2 : ℝ) / (2 * (r : ℝ)) = (1 - 1 / (r : ℝ)) * (n ^ 2 : ℝ) / 2 := by have : (r : ℝ) ≠ 0 := by positivity field_simp have h_mid : ((SimpleGraph.turanGraph n r).edgeFinset.card : ℝ) ≤ (1 - 1 / (r : ℝ)) * (n ^ 2 : ℝ) / 2 := by rwa [← heq] have hch : (n.choose 2 : ℝ) = (n : ℝ) * ((n : ℝ) - 1) / 2 := Nat.cast_choose_two ℝ n have h_sq : (1 - 1 / (r : ℝ)) * (n ^ 2 : ℝ) / 2 = (1 - 1 / (r : ℝ)) * (n.choose 2 : ℝ) + (1 - 1 / (r : ℝ)) * (n : ℝ) / 2 := by rw [hch] ring rw [h_sq] at h_mid have hr_le : (1 : ℝ) / (r : ℝ) ≤ 1 := by rw [div_le_iff₀ hr_pos] have : (1 : ℝ) ≤ (r : ℝ) := by exact_mod_cast hr linarith have : (1 - 1 / (r : ℝ)) * (n : ℝ) / 2 ≤ (n : ℝ) := by have h_nonneg : (n : ℝ) ≥ 0 := by positivity have : 1 - 1 / (r : ℝ) ≤ 1 := by have : 0 < (1 : ℝ) / (r : ℝ) := div_pos (by norm_num) hr_pos linarith nlinarith linarithlemma op_258_forces_of_capacity_lt_one_card_le_two (k : ℕ) (hk : 3 ≤ k) (J_card : ℕ) (hJ : (J_card : ℝ) * (1 - 1 / ((k : ℝ) - 1)) ≤ 1) : (J_card : ℝ) ≤ 2 := by have hk_sub : (2 : ℝ) ≤ (k : ℝ) - 1 := by have : (3 : ℝ) ≤ (k : ℝ) := by exact_mod_cast hk linarith have htheta : (1 / 2 : ℝ) ≤ 1 - 1 / ((k : ℝ) - 1) := by have : 1 / ((k : ℝ) - 1) ≤ 1 / 2 := by rw [div_le_div_iff₀ (by positivity) (by norm_num)] linarith linarith have : (J_card : ℝ) * (1 / 2) ≤ (J_card : ℝ) * (1 - 1 / ((k : ℝ) - 1)) := by have : 0 ≤ (J_card : ℝ) := by positivity nlinarith linarith/-- Capacity test: if the capped profile sums below 1, the profile forces a monochromatic K_k. -/theorem op_258_forces_of_capacity_lt_one (a : ℕ+ → ℝ) (k : ℕ) (hk : 2 ≤ k) (hcap : (∑' i : ℕ+, ENNReal.ofReal (min (a i) (1 - 1 / ((k : ℝ) - 1)))) < 1) : op_258_forces a k := by rcases eq_or_lt_of_le hk with rfl | hk3 · exact op_258_forces_two a · set θ : ℝ := 1 - 1 / ((k : ℝ) - 1) have hk_sub : (2 : ℝ) ≤ (k : ℝ) - 1 := by have : (3 : ℝ) ≤ (k : ℝ) := by exact_mod_cast hk3 linarith have hθ_ge : (1 / 2 : ℝ) ≤ θ := by have : 1 / ((k : ℝ) - 1) ≤ 1 / 2 := by rw [div_le_div_iff₀ (by positivity) (by norm_num)] linarith linarith have hθ_pos : 0 < θ := by linarith set S : ENNReal := ∑' i : ℕ+, ENNReal.ofReal (min (a i) θ) have hne : S ≠ ⊤ := ne_of_lt (hcap.trans_le le_top) have hS_lt : S.toReal < 1 := by have h_lt := (ENNReal.toReal_lt_toReal hne (by norm_num)).mpr hcap simpa using h_lt set ε : ℝ := 1 - S.toReal have hε : 0 < ε := by linarith obtain ⟨n₀, hn₀⟩ := exists_nat_gt (4 / ε + 5) use n₀ intro n hn c hc by_contra h_no have hn_pos : 0 < (n : ℝ) := by have : 0 < 4 / ε + 5 := by positivity have : 4 / ε + 5 < (n : ℝ) := hn₀.trans_le (by exact_mod_cast hn) linarith have hn2 : 2 ≤ n := by have : (2 : ℝ) ≤ (n : ℝ) := by have : 0 < 4 / ε := div_pos (by norm_num) hε have : 4 / ε + 5 < (n : ℝ) := hn₀.trans_le (by exact_mod_cast hn) linarith exact_mod_cast this have hpos : 0 < (n.choose 2 : ℝ) := by have : 0 < n.choose 2 := Nat.choose_pos hn2 exact_mod_cast this set r := k - 1 have hr : 1 ≤ r := by omega have hr_add : r + 1 = k := by omega have hr_cast : (r : ℝ) = (k : ℝ) - 1 := by simpa using Nat.cast_sub (R := ℝ) (by omega : 1 ≤ k) have h_turan_i : ∀ i : ℕ+, (((Finset.univ : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).filter (fun e => c e = i)).card : ℝ) ≤ θ * (n.choose 2 : ℝ) + n := by intro i have h_not_gt : ¬ ((Finset.univ.filter (fun e => c e = i)).card > (n ^ 2 - (n % r) ^ 2) * (r - 1) / (2 * r) + (n % r).choose 2) := by intro h_gt have h_mono := op_258_mono_clique_of_fiber_gt_turan n r hr c i h_gt rw [hr_add] at h_mono exact h_no h_mono have h_le_turan : ((Finset.univ.filter (fun e => c e = i)).card : ℝ) ≤ (((n ^ 2 - (n % r) ^ 2) * (r - 1) / (2 * r) + (n % r).choose 2 : ℕ) : ℝ) := by have : (Finset.univ.filter (fun e => c e = i)).card ≤ (n ^ 2 - (n % r) ^ 2) * (r - 1) / (2 * r) + (n % r).choose 2 := by omega exact_mod_cast this have hturan := op_258_forces_of_capacity_lt_one_turan_bound_le n r hr rw [hr_cast] at hturan exact h_le_turan.trans hturan set U := Finset.univ.image c set J := U.filter (fun i => θ < a i) have ha_nonneg : ∀ i ∈ U, 0 ≤ a i := by intro i hi rcases Finset.mem_image.mp hi with ⟨e, -, he⟩ have hmem : e ∈ (Finset.univ : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).filter (fun e' => c e' = i) := by simp [he] have hcard : 1 ≤ ((Finset.univ : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).filter (fun e' => c e' = i)).card := Finset.card_pos.mpr ⟨e, hmem⟩ have hcard_real : (1 : ℝ) ≤ (((Finset.univ : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).filter (fun e' => c e' = i)).card : ℝ) := by exact_mod_cast hcard have hle_i := hc i have : 0 < a i * (n.choose 2 : ℝ) := by linarith exact nonneg_of_mul_nonneg_left (by linarith) hpos have hmin_nonneg : ∀ i ∈ U, 0 ≤ min (a i) θ := by intro i hi exact le_min (ha_nonneg i hi) (le_of_lt hθ_pos) have h1 : ∑ i ∈ U, ENNReal.ofReal (min (a i) θ) ≤ S := ENNReal.sum_le_tsum U have hne1 : (∑ i ∈ U, ENNReal.ofReal (min (a i) θ)) ≠ ⊤ := ne_of_lt (h1.trans_lt (hcap.trans_le le_top)) have h_sum_le := (ENNReal.toReal_le_toReal hne1 hne).mpr h1 rw [← ENNReal.ofReal_sum_of_nonneg hmin_nonneg] at h_sum_le rw [ENNReal.toReal_ofReal (Finset.sum_nonneg hmin_nonneg)] at h_sum_le have hJ_sub : J ⊆ U := Finset.filter_subset _ _ have h_subsum : (∑ i ∈ J, min (a i) θ) ≤ ∑ i ∈ U, min (a i) θ := Finset.sum_le_sum_of_subset_of_nonneg hJ_sub (fun i hi _ => hmin_nonneg i hi) have hJ_eq : ∀ i ∈ J, min (a i) θ = θ := by intro i hi have : θ < a i := (Finset.mem_filter.mp hi).2 exact min_eq_right (le_of_lt this) have hJ_sum : (∑ i ∈ J, min (a i) θ) = (J.card : ℝ) * θ := by rw [Finset.sum_congr rfl hJ_eq, Finset.sum_const, nsmul_eq_mul] have hJ_le_S : (J.card : ℝ) * θ ≤ S.toReal := by linarith have hJ_le_two : (J.card : ℝ) ≤ 2 := op_258_forces_of_capacity_lt_one_card_le_two k hk3 J.card (by linarith) have hJ_mul_le : (J.card : ℝ) * (n : ℝ) ≤ 2 * (n : ℝ) := by nlinarith set fib := fun i : ℕ+ => (((Finset.univ : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).filter (fun e => c e = i)).card : ℝ) have hJ_fib : ∀ i ∈ J, fib i ≤ min (a i) θ * (n.choose 2 : ℝ) + n := by intro i hi rw [hJ_eq i hi] exact h_turan_i i have hnotJ_fib : ∀ i ∈ U.filter (fun x => ¬ (θ < a x)), fib i ≤ min (a i) θ * (n.choose 2 : ℝ) := by intro i hi have hnot : ¬ (θ < a i) := (Finset.mem_filter.mp hi).2 have hle : a i ≤ θ := not_lt.mp hnot have heq : min (a i) θ = a i := min_eq_left hle rw [heq] exact hc i have h_fib_sum : ∑ i ∈ U, fib i ≤ (∑ i ∈ U, min (a i) θ) * (n.choose 2 : ℝ) + (J.card : ℝ) * (n : ℝ) := by have h1 : ∑ i ∈ U, fib i = (∑ i ∈ J, fib i) + ∑ i ∈ U.filter (fun x => ¬ (θ < a x)), fib i := (Finset.sum_filter_add_sum_filter_not U (fun x => θ < a x) fib).symm have h2 : ∑ i ∈ U, min (a i) θ = (∑ i ∈ J, min (a i) θ) + ∑ i ∈ U.filter (fun x => ¬ (θ < a x)), min (a i) θ := (Finset.sum_filter_add_sum_filter_not U (fun x => θ < a x) (fun i => min (a i) θ)).symm rw [h1, h2, add_mul] have s1 : ∑ i ∈ J, fib i ≤ ∑ i ∈ J, (min (a i) θ * (n.choose 2 : ℝ) + n) := Finset.sum_le_sum hJ_fib have s2 : ∑ i ∈ U.filter (fun x => ¬ (θ < a x)), fib i ≤ ∑ i ∈ U.filter (fun x => ¬ (θ < a x)), (min (a i) θ * (n.choose 2 : ℝ)) := Finset.sum_le_sum hnotJ_fib rw [Finset.sum_add_distrib, Finset.sum_const, nsmul_eq_mul] at s1 rw [← Finset.sum_mul] at s1 rw [← Finset.sum_mul] at s2 linarith have h_card_fiber : ∑ i ∈ U, fib i = (n.choose 2 : ℝ) := op_258_card_fiber_sum n c have h_le_almost : (n.choose 2 : ℝ) ≤ S.toReal * (n.choose 2 : ℝ) + 2 * (n : ℝ) := by calc (n.choose 2 : ℝ) = ∑ i ∈ U, fib i := h_card_fiber.symm _ ≤ (∑ i ∈ U, min (a i) θ) * (n.choose 2 : ℝ) + (J.card : ℝ) * (n : ℝ) := h_fib_sum _ ≤ S.toReal * (n.choose 2 : ℝ) + 2 * (n : ℝ) := by have : (∑ i ∈ U, min (a i) θ) * (n.choose 2 : ℝ) ≤ S.toReal * (n.choose 2 : ℝ) := by nlinarith linarith have h_le_fin : ε * (n.choose 2 : ℝ) ≤ 2 * (n : ℝ) := by linarith have hch : (n.choose 2 : ℝ) = (n : ℝ) * ((n : ℝ) - 1) / 2 := Nat.cast_choose_two ℝ n rw [hch] at h_le_fin have hn_gt : 4 / ε + 5 < (n : ℝ) := hn₀.trans_le (by exact_mod_cast hn) have h4 : 4 < ε * ((n : ℝ) - 1) := by have h1 : 4 / ε < (n : ℝ) - 1 := by linarith have h2 := (div_lt_iff₀ hε).mp h1 linarith have : 2 * (n : ℝ) < ε * ((n : ℝ) * ((n : ℝ) - 1) / 2) := by have : 4 * (n : ℝ) < ε * ((n : ℝ) - 1) * (n : ℝ) := by nlinarith linarith linarith