AFTD Auto-Formalizing Theoretical Domains

op_258_card_fiber_tail_le

theoremverified

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.

  1. 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.

    lines 8–10

      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 : ℕ))
  2. 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.

    lines 11–14

    uses Finset.mem_coe, Finset.mem_filter, Finset.mem_image_of_mem, Finset.mem_univ

      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⟩
  3. 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.

    lines 15–16

    uses Finset.card_eq_sum_card_fiberwise

      have hfiber : s.card = ∑ i ∈ t, (s.filter (fun e => c e = i)).card :=
        Finset.card_eq_sum_card_fiberwise hmaps
  4. 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.

    lines 17–31

    uses Finset.mem_filter, Finset.mem_univ, true_and

      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
  5. 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}|.

    lines 32–39

    uses Finset.sum_congr

      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]
  6. 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.

    lines 40–44

    uses Finset.sum_le_sum

      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
  7. 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.

    lines 45–46

    uses Finset.sum_mul

      rw [← 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.

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

/-- 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
See it in the graphDiscuss this resultChallenge it