ordered_biclique_minimum_incidence_intervals
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
- binary_partial_word_cube_minimum_incidenceFor pairwise conflicting finite partial words, if total support size plus 2^m equals the number of words times m+1, then their volume sum…
- binary_partial_word_cube_cover_of_volume_eqPairwise conflicting partial words whose rational volume sum is one cover the entire finite Boolean cube.
- binary_partial_word_partition_order_convexIn a finite Boolean cube partition with one more part than mentioned coordinates, linearly order the parts so that every false occurrence…
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - binary_partial_word_cubeThe finite Boolean cube determined by fixing the coordinates of a finite support to the values of a Boolean word.
- Used by 1
- ordered_biclique_dyadic_tree_intervalsA nonempty biclique at each cut of Fin g, separated by that cut and covering every ordered pair, has interval sides when each biclique…
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.
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.
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)
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.
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
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.
uses
lt_or_gt_of_ne,mem_inter,mem_filter,mem_univ,true_and,mem_union,Or.inr,Or.inlhave 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]
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.
uses
Fintype.card_fin,binary_partial_word_cube_minimum_incidence,binary_partial_word_cube_cover_of_volume_eqhave 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
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.
uses
mem_filter,mem_univhave hess : ∀ r, ∃ i, r ∈ s i := by intro r obtain ⟨i, hi⟩ := hne r exact ⟨i, mem_filter.mpr ⟨mem_univ _, hi⟩⟩
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.
uses
Fintype.card_finhave hcard : Fintype.card (Fin g) = Fintype.card (Fin (g-1)) + 1 := by simp only [Fintype.card_fin] omega
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.
uses
mem_filter,mem_unionhave 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
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.
uses
binary_partial_word_partition_order_convexhave hconvex := binary_partial_word_partition_order_convex (g-1) s b hconflict hfull hess (by simp) hcard horder
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.
constructorEach 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.
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
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.
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.
- The proof translates the graph-theoretic problem into Boolean hypercube partitions, utilizing existing theorems for partial binary words to establish order-convexity of the combined incidence sets.
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_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