biclique_incidence_sum
For finite disjoint-sided bicliques, total vertex incidence counted by vertices equals total side cardinality counted by bicliques.
Statement
theorem biclique_incidence_sum {I R : Type*} [Fintype I] [Fintype R] [DecidableEq I] (A B : R → Finset I) (hdis : ∀ r, Disjoint (A r) (B r)) : (∑ i, (univ.filter (fun r => i ∈ A r ∪ B r)).card) = ∑ r, ((A r).card + (B r).card)
- Source
- Uniform full-root-gap and current-scale fullness reduction for OP-205 / RT-1 following arXiv:2610.15635. The reusable finite ordered-cover classification formalizes the deficiency-one structure described in arXiv:1103.3693 Corollary 2.5.6. Explicit full-class or middle-fullness hypotheses remain structural assumptions where used; optimal original counts have not been shown to imply them. No graph covering value or research advance is claimed.
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- ordered_biclique_dyadic_tree_incidenceFor g at least 2^(m-1), m positive, a family of g-1 disjoint-sided bicliques whose side sizes equal one plus their dyadic pair counts and…
The proof, explained
The theorem is proved by a double-counting argument on vertex-biclique incidence pairs. By rewriting cardinalities as sums of indicator functions and swapping the summation order, the total incidence counted over vertices is shown to equal the sum of biclique sizes ∑ r, |A r ∪ B r|. Because each biclique has disjoint sides A r and B r, the cardinality |A r ∪ B r| splits termwise into |A r| + |B r|, completing the proof.
The total incidence counted over vertices equals the sum of biclique sizes: ∑ i, |{r | i ∈ A r ∪ B r}| = ∑ r, |A r ∪ B r|.
We establish this intermediate identity (he) via double counting. Using classical decidability, card_eq_sum_ones and sum_filter rewrite the set cardinalities into sums of indicator functions (1 if i ∈ A r ∪ B r else 0). Exchanging the order of summation with sum_comm shifts the sum over R to the outside and the sum over I to the inside. By sum_congr, it suffices to equate the inner sums for each r ∈ R: applying sum_filter in reverse rewrites the indicator sum back to a sum of 1s over {i ∈ univ | i ∈ A r ∪ B r}, which filter_mem_eq_inter and univ_inter simplify to the sum of 1s over A r ∪ B r, matching |A r ∪ B r|.
uses
card_eq_sum_ones,sum_filter,sum_comm,sum_congr,filter_mem_eq_inter,univ_interclassical have he : (∑ i, (univ.filter (fun r => i ∈ A r ∪ B r)).card) = ∑ r, (A r ∪ B r).card := by simp only [card_eq_sum_ones, sum_filter] rw [sum_comm] apply sum_congr rfl intro r hr rw [← sum_filter] simp only [filter_mem_eq_inter, univ_inter]
It suffices to show that ∑ r, |A r ∪ B r| = ∑ r, (|A r| + |B r|).
Rewriting the left-hand side of the goal with the double-counting identity he replaces the vertex-incidence sum with the sum of biclique sizes ∑ r, |A r ∪ B r|.
rw [he]For each r ∈ R, |A r ∪ B r| = |A r| + |B r|, completing the equality of sums.
By hypothesis hdis, the sets A r and B r are disjoint for every r, so card_union_of_disjoint equates |A r ∪ B r| with |A r| + |B r|. Applying sum_congr with reflexivity on the index sets matches the terms across the summation over R.
uses
sum_congr,card_union_of_disjointexact sum_congr rfl (fun r hr => card_union_of_disjoint (hdis r))
card_eq_sum_ones- The cardinality of a finite set s equals the sum of 1 over all elements of s.
card_union_of_disjoint- If two finite sets are disjoint, the cardinality of their union is the sum of their cardinalities.
filter_mem_eq_inter- Filtering a finite set s by membership in a finite set t yields the intersection s ∩ t.
sum_comm- The order of summation in a finite double sum can be swapped.
sum_congr- Two finite sums are equal if their index sets are equal and their summands agree on every element of the index set.
sum_filter- The sum of a function over elements of s satisfying a predicate p equals the sum over all elements of s of the indicator if p a then f a else 0.
univ_inter- The intersection of the universal finite set with any finite subset s is s itself.
- On paper, exchanging the order of summation in a double counting argument is often treated as immediate; in Lean, it requires explicitly converting set cardinalities to sums of indicator functions (if ... then 1 else 0), swapping the sums with sum_comm, and simplifying the filtered universal set back to the original set.
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.
open Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000theorem biclique_incidence_sum {I R : Type*} [Fintype I] [Fintype R] [DecidableEq I] (A B : R → Finset I) (hdis : ∀ r, Disjoint (A r) (B r)) : (∑ i, (univ.filter (fun r => i ∈ A r ∪ B r)).card) = ∑ r, ((A r).card + (B r).card) := by classical have he : (∑ i, (univ.filter (fun r => i ∈ A r ∪ B r)).card) = ∑ r, (A r ∪ B r).card := by simp only [card_eq_sum_ones, sum_filter] rw [sum_comm] apply sum_congr rfl intro r hr rw [← sum_filter] simp only [filter_mem_eq_inter, univ_inter] rw [he] exact sum_congr rfl (fun r hr => card_union_of_disjoint (hdis r))