ordered_biclique_dyadic_tree_intervals
A nonempty biclique at each cut of Fin g, separated by that cut and covering every ordered pair, has interval sides when each biclique satisfies the dyadic tree cardinality identity and dyadic forward pairs have unique owners, with m positive and g at least 2^(m-1).
Statement
theorem ordered_biclique_dyadic_tree_intervals (g m : ℕ) (hm : 1 ≤ m) (hlo : 2^(m-1) ≤ g) (A B : Fin (g-1) → Finset (Fin g)) (hA : ∀ r i, i ∈ A r → r.val < i.val) (hB : ∀ r i, i ∈ B r → i.val ≤ r.val) (hne : ∀ r, (A r ∪ B r).Nonempty) (hcover : ∀ i j : Fin g, i < j → ∃ r, i ∈ B r ∧ j ∈ A r) (htree : ∀ r, (A r).card + (B r).card = 1 + (range m).sum (fun j => (((A r).product (B r)).filter (fun p : Fin g × Fin g => p.2.val+2^j = p.1.val)).card)) (hunique : ∀ j < m, ∀ i k : Fin g, k.val+2^j = i.val → ∃! r, i ∈ A r ∧ k ∈ B r) : (∀ r (i j k : Fin g), i ≤ j → j ≤ k → i ∈ A r → k ∈ A r → j ∈ A r) ∧ (∀ r (i j k : Fin g), i ≤ j → j ≤ k → i ∈ B r → k ∈ B r → j ∈ B r)
- 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- Built on 2
- ordered_biclique_minimum_incidence_intervalsLet g be positive and take g-1 bicliques indexed by cuts r+1 of the ordered set Fin g, with the first side strictly above r and the second…
- 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…
- Used by 1
- cycle_power_dyadic_full_gap_sides_convexIn a tight exact full ordinary-coverage dyadic model, all compressed sides between full roots zero and g are intervals when g lies between…
The proof, explained
The theorem establishes that the sides of each biclique A(r) and B(r) are intervals by reducing to the characterization of minimum-incidence ordered biclique covers. First, the lower bound 2^(m-1) ≤ g ensures g > 0, and the cut-separation conditions guarantee that A(r) and B(r) are disjoint for every r. Using this disjointness, the dyadic tree cardinality identity and uniqueness of dyadic forward pairs imply, via ordered_biclique_dyadic_tree_incidence, that the total incidence achieves the minimum bound. Finally, ordered_biclique_minimum_incidence_intervals concludes that any covering achieving this bound has interval sides.
g is strictly positive.
Since 2^(m - 1) > 0 by Nat.two_pow_pos and 2^(m - 1) ≤ g by assumption hlo, transitivity of strict inequality (lt_of_lt_of_le) gives 0 < g.
uses
lt_of_lt_of_le,Nat.two_pow_poshave hg : 0 < g := lt_of_lt_of_le (Nat.two_pow_pos _) hloFor each cut r, the sets A(r) and B(r) are disjoint.
By disjoint_left.mpr, it suffices to show that no vertex i can belong to both A(r) and B(r). If i ∈ A(r), then r < i by hA. If i ∈ B(r), then i ≤ r by hB. These two inequalities are contradictory, and omega closes the goal by integer linear arithmetic.
uses
disjoint_left.mprhave hdis (r : Fin (g-1)) : Disjoint (A r) (B r) := by apply disjoint_left.mpr intro i hi hbi have := hA r i hi have := hB r i hbi omega
For every cut r, the sides A(r) and B(r) are intervals in Fin g.
With disjointness established, ordered_biclique_dyadic_tree_incidence proves that the total incidence plus 2^m equals g*(m + 1). Supplying this incidence equality along with the separation, nonemptiness, and covering hypotheses to ordered_biclique_minimum_incidence_intervals concludes that every A(r) and B(r) is an interval.
uses
ordered_biclique_minimum_incidence_intervals,ordered_biclique_dyadic_tree_incidenceexact ordered_biclique_minimum_incidence_intervals g m hg A B hA hB hne hcover (ordered_biclique_dyadic_tree_incidence g m hm hlo A B hdis htree hunique)
lt_of_lt_of_le- If a < b and b ≤ c, then a < c.
Nat.two_pow_pos- For any natural number w, 2^w is strictly positive.
disjoint_left.mpr- Two sets are disjoint if no element belonging to the first also belongs to the second.
ordered_biclique_dyadic_tree_incidence- Under separation and disjointness, if bicliques satisfy the dyadic tree cardinality identity and cover dyadic forward pairs uniquely, their total incidence satisfies ∑_i |{r : i ∈ A r ∪ B r}| + 2^m = g*(m+1).
ordered_biclique_minimum_incidence_intervals- An ordered biclique covering of all pairs i < j achieving the minimum incidence sum g*(m+1) - 2^m has the property that each A(r) and B(r) is an interval.
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 ordered_biclique_dyadic_tree_intervals (g m : ℕ) (hm : 1 ≤ m) (hlo : 2^(m-1) ≤ g) (A B : Fin (g-1) → Finset (Fin g)) (hA : ∀ r i, i ∈ A r → r.val < i.val) (hB : ∀ r i, i ∈ B r → i.val ≤ r.val) (hne : ∀ r, (A r ∪ B r).Nonempty) (hcover : ∀ i j : Fin g, i < j → ∃ r, i ∈ B r ∧ j ∈ A r) (htree : ∀ r, (A r).card + (B r).card = 1 + (range m).sum (fun j => (((A r).product (B r)).filter (fun p : Fin g × Fin g => p.2.val+2^j = p.1.val)).card)) (hunique : ∀ j < m, ∀ i k : Fin g, k.val+2^j = i.val → ∃! r, i ∈ A r ∧ k ∈ B r) : (∀ r (i j k : Fin g), i ≤ j → j ≤ k → i ∈ A r → k ∈ A r → j ∈ A r) ∧ (∀ r (i j k : Fin g), i ≤ j → j ≤ k → i ∈ B r → k ∈ B r → j ∈ B r) := by have hg : 0 < g := lt_of_lt_of_le (Nat.two_pow_pos _) hlo have hdis (r : Fin (g-1)) : Disjoint (A r) (B r) := by apply disjoint_left.mpr intro i hi hbi have := hA r i hi have := hB r i hbi omega exact ordered_biclique_minimum_incidence_intervals g m hg A B hA hB hne hcover (ordered_biclique_dyadic_tree_incidence g m hm hlo A B hdis htree hunique)