AFTD Auto-Formalizing Theoretical Domains

ordered_biclique_minimum_incidence_intervals

theoremverified

Let 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 side at most r. Suppose every biclique is nonempty, every ordered pair is covered, and the sum over vertices of their numbers of incident bicliques plus 2^m equals g(m+1). Then each side of each biclique is order-convex.

Statement

theorem ordered_biclique_minimum_incidence_intervals
    (g m : ℕ) (hg : 0 < 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)
    (hcost : (∑ i : Fin g, (univ.filter
      (fun r : Fin (g-1) => i ∈ A r ∪ B r)).card) + 2^m = g*(m+1)) :
    (∀ 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
Reusable finite-cube and ordered-biclique helpers for the uniform OP-205 / RT-1 full-root-gap reduction following arXiv:2610.15635. The deficiency-one singular-coordinate/tree argument formalizes the Boolean setting of arXiv:1103.3693 Lemma 2.5.4 and Corollary 2.5.6; arXiv:2212.14685 Section 2.3 gives a related partition-size discussion. These are helper formalizations, not an original graph covering result; no advance is claimed.
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
Used by 1

The proof, explained

The proof models the g-1 bicliques as partial binary words over {0, ..., g-2} defined on the incidence sets of the g vertices, with bits indicating whether a vertex lies in A_r or B_r. Because bicliques cover every ordered pair, distinct vertices yield conflicting partial words that define disjoint subcubes in the hypercube. The minimum incidence cost equality forces these subcubes to have total volume 1 and thus partition the hypercube, which via an existing theorem implies that each biclique's incidence set A_r ∪ B_r is order-convex. Finally, the cut condition B_r ≤ r < A_r ensures that neither side can contain an intervening vertex from the other, proving that A_r and B_r are individually order-convex intervals.

  1. Define the incidence set s(i) and the bit assignment b(i, r) for each vertex i ∈ Fin g and biclique r ∈ Fin (g-1).

    For each vertex i, we set s(i) = {r | i ∈ A_r ∪ B_r} to be the bicliques containing i, and b(i, r) to be true if i ∈ A_r and false otherwise. Classical logic is enabled for decidability.

    lines 16–19

      classical
      let s : Fin g → Finset (Fin (g-1)) := fun i =>
        univ.filter (fun r => i ∈ A r ∪ B r)
      let b : Fin g → Fin (g-1) → Bool := fun i r => decide (i ∈ A r)
  2. For each biclique r, the sets A_r and B_r are disjoint.

    If a vertex i belonged to both A_r and B_r, we would have r < i (from i ∈ A_r) and i ≤ r (from i ∈ B_r), which is impossible by linear arithmetic.

    lines 20–24

      have hdis (r : Fin (g-1)) (i : Fin g) (hi : i ∈ B r) : i ∉ A r := by
        intro ha
        have := hA r i ha
        have := hB r i hi
        omega
  3. Any two distinct vertices i ≠ j define conflicting partial words: they share some biclique r on which their bit assignments differ.

    By linearity of the order, either i < j or j < i. If i < j, the covering hypothesis yields a biclique r such that i ∈ B_r and j ∈ A_r. Then r ∈ s(i) ∩ s(j), and by disjointness b(i, r) = false ≠ true = b(j, r). The case j < i is symmetric.

    lines 25–37

    uses lt_or_gt_of_ne, mem_inter, mem_filter, mem_univ, true_and, mem_union, Or.inr, Or.inl

      have hconflict : ∀ i j, i ≠ j → ∃ r ∈ s i ∩ s j, b i r ≠ b j r := by
        intro i j hij
        rcases lt_or_gt_of_ne hij with hlt | hgt
        · obtain ⟨r, hir, hjr⟩ := hcover i j hlt
          refine ⟨r, ?_, ?_⟩
          · simp only [s, mem_inter, mem_filter, mem_univ, true_and, mem_union]
            exact ⟨Or.inr hir, Or.inl hjr⟩
          · simp [b, hdis r i hir, hjr]
        · obtain ⟨r, hjr, hir⟩ := hcover j i hgt
          refine ⟨r, ?_, ?_⟩
          · simp only [s, mem_inter, mem_filter, mem_univ, true_and, mem_union]
            exact ⟨Or.inl hir, Or.inr hjr⟩
          · simp [b, hir, hdis r j hjr]
  4. The subcubes associated with the vertices cover the entire Boolean hypercube {0, 1}^(g-1).

    Rewriting the incidence cost hypothesis with Fintype.card_fin gives the standard form of the minimum incidence equality. By binary_partial_word_cube_minimum_incidence, the subcubes have total volume ∑ 2^(-|s(i)|) = 1. Consequently, binary_partial_word_cube_cover_of_volume_eq shows that their union covers the entire hypercube.

    lines 38–41

    uses Fintype.card_fin, binary_partial_word_cube_minimum_incidence, binary_partial_word_cube_cover_of_volume_eq

      have heqcost : (∑ i, (s i).card) + 2^m = Fintype.card (Fin g)*(m+1) := by
        simpa only [s, Fintype.card_fin] using hcost
      have hvolume := (binary_partial_word_cube_minimum_incidence s b m hconflict heqcost).1
      have hfull := binary_partial_word_cube_cover_of_volume_eq s b hconflict hvolume
  5. Every biclique r is essential: there is at least one vertex incident to r.

    This is an immediate unpacking of the hypothesis that each biclique A_r ∪ B_r is nonempty.

    lines 42–45

    uses mem_filter, mem_univ

      have hess : ∀ r, ∃ i, r ∈ s i := by
        intro r
        obtain ⟨i, hi⟩ := hne r
        exact ⟨i, mem_filter.mpr ⟨mem_univ _, hi⟩⟩
  6. The number of vertices |Fin g| equals |Fin (g-1)| + 1.

    The cardinality of Fin n is n, and g = (g - 1) + 1 holds since g > 0.

    lines 46–48

    uses Fintype.card_fin

      have hcard : Fintype.card (Fin g) = Fintype.card (Fin (g-1)) + 1 := by
        simp only [Fintype.card_fin]
        omega
  7. If vertices i and j are both incident to biclique r with b(i, r) = false and b(j, r) = true, then i < j.

    The bit conditions imply i ∈ B_r and j ∈ A_r. The defining cut inequalities of the biclique give i ≤ r < j, so i < j.

    lines 49–57

    uses mem_filter, mem_union

      have horder : ∀ r i j, r ∈ s i → r ∈ s j → b i r = false → b j r = true → i < j := by
        intro r i j hi hj hbi hbj
        have hir : i ∈ A r ∪ B r := (mem_filter.mp hi).2
        have hiB : i ∈ B r := (mem_union.mp hir).resolve_left (by simpa [b] using hbi)
        have hjA : j ∈ A r := by simpa [b] using hbj
        have := hA r j hjA
        have := hB r i hiB
        change i.val < j.val
        omega
  8. For every biclique r, the combined incidence set A_r ∪ B_r is order-convex: if i ≤ j ≤ k and r ∈ s(i) and r ∈ s(k), then r ∈ s(j).

    All conditions of the theorem binary_partial_word_partition_order_convex have been verified: pairwise conflict, full hypercube coverage, essentiality of every coordinate, the dimension matching g-1, the vertex count being (g-1)+1, and compatibility of bits with the vertex ordering.

    lines 58–59

    uses binary_partial_word_partition_order_convex

      have hconvex := binary_partial_word_partition_order_convex (g-1)
        s b hconflict hfull hess (by simp) hcard horder
  9. It suffices to show separately that each A_r is order-convex and each B_r is order-convex.

    The goal is a conjunction of two order-convexity statements, which constructor splits into two subgoals.

    line 60

      constructor
  10. Each side A_r is order-convex: if i ≤ j ≤ k and i, k ∈ A_r, then j ∈ A_r.

    Since i, k ∈ A_r, we have r ∈ s(i) and r ∈ s(k). By order-convexity of the incidence set, r ∈ s(j), so j ∈ A_r ∪ B_r. If j ∈ B_r, then j ≤ r < i, which contradicts i ≤ j. Thus j must belong to A_r.

    lines 61–71

    uses mem_filter, mem_univ, mem_union, Or.inl

      · intro r i j k hij hjk hi hk
        have his : r ∈ s i := mem_filter.mpr ⟨mem_univ _, mem_union.mpr (Or.inl hi)⟩
        have hks : r ∈ s k := mem_filter.mpr ⟨mem_univ _, mem_union.mpr (Or.inl hk)⟩
        have hjs := hconvex r i j k hij hjk his hks
        have hjr := (mem_filter.mp hjs).2
        rcases mem_union.mp hjr with ha | hb
        · exact ha
        · have := hA r i hi
          have := hB r j hb
          have : i.val ≤ j.val := hij
          omega
  11. Each side B_r is order-convex: if i ≤ j ≤ k and i, k ∈ B_r, then j ∈ B_r.

    Since i, k ∈ B_r, we have r ∈ s(i) and r ∈ s(k). By order-convexity of the incidence set, r ∈ s(j), so j ∈ A_r ∪ B_r. If j ∈ A_r, then k ≤ r < j, which contradicts j ≤ k. Thus j must belong to B_r.

    lines 72–82

    uses mem_filter, mem_univ, mem_union, Or.inr

      · intro r i j k hij hjk hi hk
        have his : r ∈ s i := mem_filter.mpr ⟨mem_univ _, mem_union.mpr (Or.inr hi)⟩
        have hks : r ∈ s k := mem_filter.mpr ⟨mem_univ _, mem_union.mpr (Or.inr hk)⟩
        have hjs := hconvex r i j k hij hjk his hks
        have hjr := (mem_filter.mp hjs).2
        rcases mem_union.mp hjr with ha | hb
        · have := hA r j ha
          have := hB r k hk
          have : j.val ≤ k.val := hjk
          omega
        · exact hb
lt_or_gt_of_ne
In a linear order, two unequal elements satisfy either a < b or b < a.
mem_inter
An element belongs to the intersection of two finite sets if and only if it belongs to both sets.
mem_filter
An element belongs to the filtered finset {x ∈ s | p(x)} if and only if it belongs to s and satisfies p.
mem_univ
Every element of a finite type belongs to the universal finite set univ.
true_and
The logical conjunction (True ∧ p) simplifies to p.
mem_union
An element belongs to the union of two finite sets if and only if it belongs to at least one of them.
Or.inr
Constructs a proof of a ∨ b from a proof of the right disjunct b.
Or.inl
Constructs a proof of a ∨ b from a proof of the left disjunct a.
Fintype.card_fin
The cardinality of Fin n is n.
binary_partial_word_cube_minimum_incidence
If pairwise conflicting partial binary words satisfy the minimum incidence equality ∑ |s(i)| + 2^m = |I|(m + 1), then the total volume of their associated subcubes equals 1.
binary_partial_word_cube_cover_of_volume_eq
If pairwise conflicting partial binary words have subcubes whose total volume sum equals 1, then their union covers the entire Boolean hypercube.
binary_partial_word_partition_order_convex
In an essential cube partition of {0, 1}^n into n + 1 linearly ordered subcubes compatible with the bit order, the incidence set of each coordinate is order-convex.

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

open Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000theorem ordered_biclique_minimum_incidence_intervals    (g m : ℕ) (hg : 0 < 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)    (hcost : (∑ i : Fin g, (univ.filter      (fun r : Fin (g-1) => i ∈ A r ∪ B r)).card) + 2^m = g*(m+1)) :    (∀ 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  classical  let s : Fin g → Finset (Fin (g-1)) := fun i =>    univ.filter (fun r => i ∈ A r ∪ B r)  let b : Fin g → Fin (g-1) → Bool := fun i r => decide (i ∈ A r)  have hdis (r : Fin (g-1)) (i : Fin g) (hi : i ∈ B r) : i ∉ A r := by    intro ha    have := hA r i ha    have := hB r i hi    omega  have hconflict : ∀ i j, i ≠ j → ∃ r ∈ s i ∩ s j, b i r ≠ b j r := by    intro i j hij    rcases lt_or_gt_of_ne hij with hlt | hgt    · obtain ⟨r, hir, hjr⟩ := hcover i j hlt      refine ⟨r, ?_, ?_⟩      · simp only [s, mem_inter, mem_filter, mem_univ, true_and, mem_union]        exact ⟨Or.inr hir, Or.inl hjr⟩      · simp [b, hdis r i hir, hjr]    · obtain ⟨r, hjr, hir⟩ := hcover j i hgt      refine ⟨r, ?_, ?_⟩      · simp only [s, mem_inter, mem_filter, mem_univ, true_and, mem_union]        exact ⟨Or.inl hir, Or.inr hjr⟩      · simp [b, hir, hdis r j hjr]  have heqcost : (∑ i, (s i).card) + 2^m = Fintype.card (Fin g)*(m+1) := by    simpa only [s, Fintype.card_fin] using hcost  have hvolume := (binary_partial_word_cube_minimum_incidence s b m hconflict heqcost).1  have hfull := binary_partial_word_cube_cover_of_volume_eq s b hconflict hvolume  have hess : ∀ r, ∃ i, r ∈ s i := by    intro r    obtain ⟨i, hi⟩ := hne r    exact ⟨i, mem_filter.mpr ⟨mem_univ _, hi⟩⟩  have hcard : Fintype.card (Fin g) = Fintype.card (Fin (g-1)) + 1 := by    simp only [Fintype.card_fin]    omega  have horder : ∀ r i j, r ∈ s i → r ∈ s j → b i r = false → b j r = true → i < j := by    intro r i j hi hj hbi hbj    have hir : i ∈ A r ∪ B r := (mem_filter.mp hi).2    have hiB : i ∈ B r := (mem_union.mp hir).resolve_left (by simpa [b] using hbi)    have hjA : j ∈ A r := by simpa [b] using hbj    have := hA r j hjA    have := hB r i hiB    change i.val < j.val    omega  have hconvex := binary_partial_word_partition_order_convex (g-1)    s b hconflict hfull hess (by simp) hcard horder  constructor  · intro r i j k hij hjk hi hk    have his : r ∈ s i := mem_filter.mpr ⟨mem_univ _, mem_union.mpr (Or.inl hi)⟩    have hks : r ∈ s k := mem_filter.mpr ⟨mem_univ _, mem_union.mpr (Or.inl hk)⟩    have hjs := hconvex r i j k hij hjk his hks    have hjr := (mem_filter.mp hjs).2    rcases mem_union.mp hjr with ha | hb    · exact ha    · have := hA r i hi      have := hB r j hb      have : i.val ≤ j.val := hij      omega  · intro r i j k hij hjk hi hk    have his : r ∈ s i := mem_filter.mpr ⟨mem_univ _, mem_union.mpr (Or.inr hi)⟩    have hks : r ∈ s k := mem_filter.mpr ⟨mem_univ _, mem_union.mpr (Or.inr hk)⟩    have hjs := hconvex r i j k hij hjk his hks    have hjr := (mem_filter.mp hjs).2    rcases mem_union.mp hjr with ha | hb    · have := hA r j ha      have := hB r k hk      have : j.val ≤ k.val := hjk      omega    · exact hb
See it in the graphDiscuss this resultChallenge it