op_258_card_fiber_tail_le
For an a-bounded colouring c of the edges of K_n, the number of edges with colour index strictly greater than C is at most the sum of a_i over colours used exceeding C multiplied by C(n, 2).
Statement
theorem op_258_card_fiber_tail_le (a : ℕ+ → ℝ) (n : ℕ) (c : (SimpleGraph.completeGraph (Fin n)).edgeSet → ℕ+) (hc : op_258_bounded a n c) (C : ℕ) : (((Finset.univ : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).filter (fun e => C < (c e : ℕ))).card : ℝ) ≤ (∑ i ∈ (Finset.univ.image c).filter (fun (i : ℕ+) => C < (i : ℕ)), a i) * (n.choose 2 : ℝ)
- Source
- step towards op_258_forces_step
- Verified
- 22 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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 *…
The proof, explained
The total number of edges with colour index greater than C is decomposed as the sum of the cardinalities of the monochromatic fibers for all used colours i > C. By the a-boundedness hypothesis, each monochromatic fiber contains at most a_i * C(n, 2) edges. Summing these bounds over all such colours and factoring out C(n, 2) yields the desired inequality.
Define shorthand for the edge set E of K_n, the edges s with colour index greater than C, and the set t of used colours exceeding C.
Let E be the edge set of the complete graph on n vertices, let s ⊆ E be the subset of edges e with c(e) > C, and let t be the set of colours in the image of c that strictly exceed C.
let E := (SimpleGraph.completeGraph (Fin n)).edgeSet let s : Finset E := Finset.univ.filter (fun e => C < (c e : ℕ)) let t : Finset ℕ+ := (Finset.univ.image c).filter (fun (i : ℕ+) => C < (i : ℕ))
The colouring c maps edges in s into t.
For every edge e ∈ s, its colour c(e) is in the image of c on E and satisfies c(e) > C by definition of s, so c(e) ∈ t.
uses
Finset.mem_coe,Finset.mem_filter,Finset.mem_image_of_mem,Finset.mem_univhave hmaps : Set.MapsTo c (↑s : Set E) (↑t : Set ℕ+) := by intro e he rw [Finset.mem_coe, Finset.mem_filter] at he ⊢ exact ⟨Finset.mem_image_of_mem c (Finset.mem_univ e), he.2⟩
The number of edges in s decomposes as the sum over i ∈ t of the number of edges in s of colour i.
Because c maps s into t, partitioning s by the values of c(e) expresses |s| as the sum of the fiber cardinalities |{e ∈ s | c(e) = i}| over all i ∈ t.
uses
Finset.card_eq_sum_card_fiberwisehave hfiber : s.card = ∑ i ∈ t, (s.filter (fun e => c e = i)).card := Finset.card_eq_sum_card_fiberwise hmaps
For every colour i ∈ t, the edges in s of colour i are all edges in E of colour i.
Every edge in s of colour i is an edge in E of colour i. Conversely, if an edge e ∈ E has colour c(e) = i, then since i ∈ t satisfies i > C, we have c(e) > C, which means e already belongs to s.
uses
Finset.mem_filter,Finset.mem_univ,true_andhave hfiber_eq : ∀ i ∈ t, (s.filter (fun e => c e = i)) = ((Finset.univ : Finset E).filter (fun e => c e = i)) := by intro i hi rw [Finset.mem_filter] at hi ext e simp only [Finset.mem_filter, Finset.mem_univ, true_and] constructor · intro h exact h.2 · intro h refine ⟨?_, h⟩ show e ∈ s simp only [s, Finset.mem_filter, Finset.mem_univ, true_and] rw [h] exact hi.2
In ℝ, the size of s equals the sum over i ∈ t of the full monochromatic edge set sizes.
Casting the fiber decomposition into ℝ and substituting the identity {e ∈ s | c(e) = i} = {e ∈ E | c(e) = i} for each i ∈ t rewrites the goal's left-hand side |s| as ∑_{i ∈ t} |{e ∈ E | c(e) = i}|.
uses
Finset.sum_congrhave hfiber_real : (s.card : ℝ) = ∑ i ∈ t, (((Finset.univ : Finset E).filter (fun e => c e = i)).card : ℝ) := by rw [hfiber] push_cast refine Finset.sum_congr rfl ?_ intro i hi rw [hfiber_eq i hi] rw [hfiber_real]
The sum of the monochromatic edge set sizes is at most ∑_{i ∈ t} a_i * C(n, 2).
Applying the a-boundedness hypothesis (hc) to each colour i ∈ t bounds each monochromatic fiber size |{e ∈ E | c(e) = i}| by a_i * C(n, 2). Summing these inequalities yields the bound on the sum.
uses
Finset.sum_le_sumhave hle : (∑ i ∈ t, (((Finset.univ : Finset E).filter (fun e => c e = i)).card : ℝ)) ≤ ∑ i ∈ t, (a i * (n.choose 2 : ℝ)) := by refine Finset.sum_le_sum ?_ intro i hi exact hc i
The number of edges with colour index greater than C is at most (∑_{i ∈ t} a_i) * C(n, 2).
Factoring the common term C(n, 2) out of the sum over i ∈ t transforms ∑_{i ∈ t} a_i * C(n, 2) into (∑_{i ∈ t} a_i) * C(n, 2), closing the goal.
uses
Finset.sum_mulrw [← Finset.sum_mul] at hle exact hle
Finset.mem_coe- An element belongs to a finite set coerced to a set if and only if it belongs to the finite set.
Finset.mem_filter- An element belongs to Finset.filter p s if and only if it belongs to s and satisfies p.
Finset.mem_image_of_mem- If an element a is in s, then its image f(a) is in Finset.image f s.
Finset.mem_univ- Every element of a finite type belongs to Finset.univ.
Finset.card_eq_sum_card_fiberwise- If f maps a finite set s into a finite set t, then the cardinality of s is the sum of the cardinalities of the fibers over all elements of t.
true_and- The conjunction True ∧ p is equivalent to p.
Finset.sum_congr- Two finite sums are equal if their index sets are equal and their summands agree on every index.
Finset.sum_le_sum- A sum of terms is bounded by another sum if each term is bounded by the corresponding term.
Finset.sum_mul- Distributivity of multiplication over finite summation: multiplying a sum by a scalar equals summing the scaled terms.
- Casting cardinalities from ℕ to ℝ (via push_cast) is a formal necessity to reconcile integer counts with the real-valued bound, but has no mathematical content on paper.
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.
/-- For an a-bounded colouring c of K_n, the number of edges coloured with index strictly greater than C is bounded by (∑_{i used, i > C} a_i) * C(n, 2). -/theorem op_258_card_fiber_tail_le (a : ℕ+ → ℝ) (n : ℕ) (c : (SimpleGraph.completeGraph (Fin n)).edgeSet → ℕ+) (hc : op_258_bounded a n c) (C : ℕ) : (((Finset.univ : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).filter (fun e => C < (c e : ℕ))).card : ℝ) ≤ (∑ i ∈ (Finset.univ.image c).filter (fun (i : ℕ+) => C < (i : ℕ)), a i) * (n.choose 2 : ℝ) := by let E := (SimpleGraph.completeGraph (Fin n)).edgeSet let s : Finset E := Finset.univ.filter (fun e => C < (c e : ℕ)) let t : Finset ℕ+ := (Finset.univ.image c).filter (fun (i : ℕ+) => C < (i : ℕ)) have hmaps : Set.MapsTo c (↑s : Set E) (↑t : Set ℕ+) := by intro e he rw [Finset.mem_coe, Finset.mem_filter] at he ⊢ exact ⟨Finset.mem_image_of_mem c (Finset.mem_univ e), he.2⟩ have hfiber : s.card = ∑ i ∈ t, (s.filter (fun e => c e = i)).card := Finset.card_eq_sum_card_fiberwise hmaps have hfiber_eq : ∀ i ∈ t, (s.filter (fun e => c e = i)) = ((Finset.univ : Finset E).filter (fun e => c e = i)) := by intro i hi rw [Finset.mem_filter] at hi ext e simp only [Finset.mem_filter, Finset.mem_univ, true_and] constructor · intro h exact h.2 · intro h refine ⟨?_, h⟩ show e ∈ s simp only [s, Finset.mem_filter, Finset.mem_univ, true_and] rw [h] exact hi.2 have hfiber_real : (s.card : ℝ) = ∑ i ∈ t, (((Finset.univ : Finset E).filter (fun e => c e = i)).card : ℝ) := by rw [hfiber] push_cast refine Finset.sum_congr rfl ?_ intro i hi rw [hfiber_eq i hi] rw [hfiber_real] have hle : (∑ i ∈ t, (((Finset.univ : Finset E).filter (fun e => c e = i)).card : ℝ)) ≤ ∑ i ∈ t, (a i * (n.choose 2 : ℝ)) := by refine Finset.sum_le_sum ?_ intro i hi exact hc i rw [← Finset.sum_mul] at hle exact hle