one_layered_linear_bound
For all integers r ≥ 1 and m ≥ r, the maximum number of layers F(m, r) in a 1-layered family of r-subsets on at most m vertices satisfies F(m, r) ≤ 2^(r - 1) * (m - r) + 1.
Statement
theorem one_layered_linear_bound (m r : ℕ) (hr : 1 ≤ r) (hm : r ≤ m) :
one_layered_max_layers m r ≤ 2 ^ (r - 1) * (m - r) + 1- Formalizes
- arXiv:2611.08071 Theorem 2.1
- Verified
- 08 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- one_layered_max_layersFor natural numbers m and r, one_layered_max_layers m r is the supremum (maximum) over all n ≤ m and all 1-layered families of r-subsets…
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - OneLayeredFamilyGiven a type V and a natural number r, a 1-layered family of r-subsets on V is a structure OneLayeredFamily (V : Type*) (r : ℕ) consisting…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- Used by 1
- one_layered_family_upper_boundsFor all integers r ≥ 1 and m ≥ r, the maximum number of layers F(m, r) of a 1-layered family of r-subsets on at most m vertices satisfies…
Read back from the Lean
For all natural numbers $m$ and $r$ such that $1 \le r$ and $r \le m$, the maximum number of layers one_layered_max_layers m r is at most $2^{r - 1} \cdot (m - r) + 1$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The theorem establishes the linear upper bound F(m, r) ≤ 2^(r - 1) * (m - r) + 1 by induction on the uniformity r. The base case r = 1 holds because disjointness of layers forces distinct singleton hyperedges, yielding k ≤ |U|. For the inductive step, strong induction on the number of layers k proves a strengthened block inequality; the key move finds a vertex v in the first layer that persists through the maximal layer l intersecting layer 0, forming an (r - 1)-uniform link family on the first l + 1 layers. When l + 1 < k, the remaining suffix is bounded by the strong induction hypothesis on k, and the two estimates are glued together using inclusion-exclusion and the disjointness of layer 0 from the suffix.
A vertex belongs to layer t if and only if it belongs to some hyperedge of layer t
Unfolding the definition `olb_vs F t = (F.layers t).biUnion id` directly shows that an element belongs to the vertex set of layer t precisely when it belongs to some hyperedge G in that layer.
uses
olb_vstheorem olb_mem_vs {V : Type*} [DecidableEq V] {r : ℕ} (F : OneLayeredFamily V r) (t : Fin F.k) (w : V) : w ∈ olb_vs F t ↔ ∃ G ∈ F.layers t, w ∈ G := by simp [olb_vs]
If a vertex appears in layers s and t with s ≤ u ≤ t, it appears in layer u
The interval property of 1-layered families applied to the singleton set {w} guarantees that the set of layer indices containing w forms an order-connected interval. Since w is in layer s and layer t, it must be contained in some hyperedge of every intermediate layer u.
uses
Finset.singleton_nonempty,olb_mem_vs,Finset.singleton_subset_ifftheorem olb_vs_mid {V : Type*} [DecidableEq V] {r : ℕ} (F : OneLayeredFamily V r) {w : V} {s t u : Fin F.k} (hs : w ∈ olb_vs F s) (ht : w ∈ olb_vs F t) (h1 : s ≤ u) (h2 : u ≤ t) : w ∈ olb_vs F u := by have h := (F.interval_property {w} (Finset.singleton_nonempty w)).out rw [olb_mem_vs] at hs ht ⊢ obtain ⟨G1, hG1, hw1⟩ := hs obtain ⟨G2, hG2, hw2⟩ := ht obtain ⟨G, hG, hsub⟩ := h (x := s) ⟨G1, hG1, Finset.singleton_subset_iff.mpr hw1⟩ (y := t) ⟨G2, hG2, Finset.singleton_subset_iff.mpr hw2⟩ ⟨h1, h2⟩ exact ⟨G, hG, Finset.singleton_subset_iff.mp hsub⟩
Dropping the first j layers of a 1-layered family produces a valid 1-layered family of suffix layers
The suffix family has k - j layers, each layer being F.layers (t + j). Disjointness and the interval property are inherited directly from the original family by shifting indices by j.
uses
Fin.ext,Fin.le_defdef olb_suf {V : Type*} [DecidableEq V] {r : ℕ} (F : OneLayeredFamily V r) (j : ℕ) (hj : j < F.k) : OneLayeredFamily V r where k := F.k - j k_pos := by omega layers t := F.layers ⟨t.val + j, by have := t.isLt; omega⟩ layers_nonempty t := F.layers_nonempty _ layers_card t := F.layers_card _ layers_disjoint t₁ t₂ h := F.layers_disjoint _ _ (fun e => h (Fin.ext (by have := congrArg Fin.val e; simp only at this; omega))) interval_property S hS := by have h := (F.interval_property S hS).out refine ⟨fun x hx y hy z hz => ?_⟩ have hz1 := Fin.le_def.mp hz.1 have hz2 := Fin.le_def.mp hz.2 exact h (x := ⟨x.val + j, by have := x.isLt; omega⟩) hx (y := ⟨y.val + j, by have := y.isLt; omega⟩) hy ⟨Fin.mk_le_mk.mpr (by omega), Fin.mk_le_mk.mpr (by omega)⟩
The vertex set of layer t in the suffix family is the vertex set of layer t + j in the original family
This identity holds by definition of the suffix family layers and unfolding `olb_vs`.
uses
olb_suftheorem olb_suf_vs {V : Type*} [DecidableEq V] {r : ℕ} (F : OneLayeredFamily V r) (j : ℕ) (hj : j < F.k) (t : Fin (olb_suf F j hj).k) : olb_vs (olb_suf F j hj) t = olb_vs F ⟨t.val + j, by have := t.isLt; simp [olb_suf] at this; omega⟩ := rfl
The link construction on the first m layers with respect to a common vertex v yields a 1-layered family of (r - 1)-subsets
For each layer t < m, the new layer is formed by selecting all hyperedges containing v and erasing v from each. Every such set has size r - 1. Because v can be re-inserted to recover the original hyperedge, disjointness of the original layers implies disjointness of the link layers.
uses
olb_mem_vs,Finset.card_erase_of_mem,Finset.insert_erase,Finset.disjoint_leftdef olb_link {V : Type*} [DecidableEq V] {r : ℕ} (F : OneLayeredFamily V r) (v : V) (m : ℕ) (hm0 : 0 < m) (hm : m ≤ F.k) (hv : ∀ t : Fin F.k, t.val < m → v ∈ olb_vs F t) : OneLayeredFamily V (r - 1) where k := m k_pos := hm0 layers t := ((F.layers ⟨t.val, by omega⟩).filter (fun G => v ∈ G)).image (fun G => G.erase v) layers_nonempty t := by obtain ⟨G, hG, hv'⟩ := (olb_mem_vs F _ v).mp (hv ⟨t.val, by omega⟩ t.isLt) exact ⟨G.erase v, Finset.mem_image.mpr ⟨G, Finset.mem_filter.mpr ⟨hG, hv'⟩, rfl⟩⟩ layers_card t G hG := by obtain ⟨G', hG', rfl⟩ := Finset.mem_image.mp hG rw [Finset.mem_filter] at hG' rw [Finset.card_erase_of_mem hG'.2, F.layers_card _ _ hG'.1] layers_disjoint t₁ t₂ h := by rw [Finset.disjoint_left] intro G h1 h2 obtain ⟨G1, hG1, rfl⟩ := Finset.mem_image.mp h1 obtain ⟨G2, hG2, he⟩ := Finset.mem_image.mp h2 rw [Finset.mem_filter] at hG1 hG2 have : G2 = G1 := by rw [← Finset.insert_erase hG1.2, ← Finset.insert_erase hG2.2, he] subst this exact Finset.disjoint_left.mp (F.layers_disjoint _ _ (fun e => h (Fin.ext (by have := congrArg Fin.val e; simp only at this; omega)))) hG1.1 hG2.1
The link construction inherits the interval property
For any non-empty set S not containing v, S is contained in a link hyperedge at layer t if and only if S ∪ {v} is contained in a hyperedge of the original family at layer t. By the interval property of the original family applied to S ∪ {v}, the set of such layer indices is order-connected.
uses
Finset.insert_nonempty,Fin.le_def,Finset.insert_subset,Finset.erase_subsetinterval_property S hS := by refine ⟨fun x hx y hy z hz => ?_⟩ obtain ⟨G1, hG1, hS1⟩ := hx obtain ⟨G2, hG2, hS2⟩ := hy obtain ⟨H1, hH1, rfl⟩ := Finset.mem_image.mp hG1 obtain ⟨H2, hH2, rfl⟩ := Finset.mem_image.mp hG2 rw [Finset.mem_filter] at hH1 hH2 have hvS : v ∉ S := fun h => Finset.notMem_erase v H1 (hS1 h) have h := (F.interval_property (insert v S) (Finset.insert_nonempty v S)).out have hz1 := Fin.le_def.mp hz.1 have hz2 := Fin.le_def.mp hz.2 have hxl : x.val < F.k := by have := x.isLt; omega have hyl : y.val < F.k := by have := y.isLt; omega have hzl : z.val < F.k := by have := z.isLt; omega have hx' : (⟨x.val, hxl⟩ : Fin F.k) ∈ {t : Fin F.k | ∃ G ∈ F.layers t, insert v S ⊆ G} := ⟨H1, hH1.1, Finset.insert_subset hH1.2 (hS1.trans (Finset.erase_subset v H1))⟩ have hy' : (⟨y.val, hyl⟩ : Fin F.k) ∈ {t : Fin F.k | ∃ G ∈ F.layers t, insert v S ⊆ G} := ⟨H2, hH2.1, Finset.insert_subset hH2.2 (hS2.trans (Finset.erase_subset v H2))⟩ have hzm : (⟨z.val, hzl⟩ : Fin F.k) ∈ Set.Icc (⟨x.val, hxl⟩ : Fin F.k) ⟨y.val, hyl⟩ := ⟨Fin.mk_le_mk.mpr hz1, Fin.mk_le_mk.mpr hz2⟩ obtain ⟨H3, hH3, hS3⟩ := h hx' hy' hzm refine ⟨H3.erase v, Finset.mem_image.mpr ⟨H3, Finset.mem_filter.mpr ⟨hH3, hS3 (Finset.mem_insert_self v S)⟩, rfl⟩, ?_⟩ intro w hw exact Finset.mem_erase.mpr ⟨fun e => hvS (e ▸ hw), hS3 (Finset.mem_insert_of_mem hw)⟩
The total vertex set of the link family is contained in the union of the first m layers minus {v}
Every vertex in the link family comes from some original hyperedge of layer t < m other than v, so the total vertex set is a subset of (⋃_{t < m} olb_vs F t) \ {v}. In particular, its cardinality is strictly less than the total number of vertices in those layers.
uses
olb_mem_vstheorem olb_link_U {V : Type*} [DecidableEq V] {r : ℕ} (F : OneLayeredFamily V r) (v : V) (m : ℕ) (hm0 : 0 < m) (hm : m ≤ F.k) (hv : ∀ t : Fin F.k, t.val < m → v ∈ olb_vs F t) : olb_U (olb_link F v m hm0 hm hv) ⊆ ((Finset.univ.filter (fun t : Fin F.k => t.val < m)).biUnion (olb_vs F)).erase v := by intro w hw simp only [olb_U, Finset.mem_biUnion, Finset.mem_univ, true_and, olb_vs, id] at hw obtain ⟨t, G, hG, hwG⟩ := hw obtain ⟨H, hH, rfl⟩ := Finset.mem_image.mp hG rw [Finset.mem_filter] at hH rw [Finset.mem_erase] at hwG refine Finset.mem_erase.mpr ⟨hwG.1, ?_⟩ simp only [Finset.mem_biUnion, Finset.mem_filter, Finset.mem_univ, true_and] exact ⟨⟨t.val, by have : t.val < m := t.isLt; omega⟩, t.isLt, (olb_mem_vs F _ w).mpr ⟨H, hH.1, hwG.2⟩⟩
Arithmetic lemma: linear bound holds when the maximal intersecting layer is the last layer
Using non-linear arithmetic, if k + c * r ≤ c * g + 1 with g + 1 ≤ U and a ≤ U, multiplying by c and rearranging gives k + c * (a + r + 1) ≤ c * (2 * U) + 1.
uses
Nat.mul_le_mul_lefttheorem olb_ar1 (c k a U r g : ℕ) (hG : k + c * r ≤ c * g + 1) (hg : g + 1 ≤ U) (ha : a ≤ U) : k + c * (a + (r + 1)) ≤ c * (2 * U) + 1 := by have h1 : c * (g + 1) ≤ c * U := Nat.mul_le_mul_left c hg have h2 : c * a ≤ c * U := Nat.mul_le_mul_left c ha nlinarith
Arithmetic lemma: combining prefix and suffix bounds via inclusion-exclusion
Combines the bound for the prefix link family (l1 layers) and the suffix family (d layers) using the bounds n1 + R ≤ U + a' and a + R ≤ U to deduce k + c * (a + r + 1) ≤ c * (2 * U) + 1.
uses
Nat.mul_le_mul_left,Nat.mul_le_multheorem olb_ar2 (c k l1 d a U r g n1 a' R uR : ℕ) (hc : 1 ≤ c) (hr : 1 ≤ r) (hk : k = l1 + d) (hG : l1 + c * r ≤ c * g + 1) (hg : g + 1 ≤ n1) (hR : d + c * (a' + (r + 1)) ≤ c * (2 * uR) + 1) (huR : uR ≤ R) (h3 : n1 + R ≤ U + a') (h4 : a + R ≤ U) : k + c * (a + (r + 1)) ≤ c * (2 * U) + 1 := by have m1 : c * (g + 1) ≤ c * n1 := Nat.mul_le_mul_left c hg have m2 : c * uR ≤ c * R := Nat.mul_le_mul_left c huR have m3 : c * (n1 + R) ≤ c * (U + a') := Nat.mul_le_mul_left c h3 have m4 : c * (a + R) ≤ c * U := Nat.mul_le_mul_left c h4 have m5 : 1 * 2 ≤ c * (r + 1) := Nat.mul_le_mul hc (by omega) subst hk nlinarith
Base case r = 1: the number of layers is at most the total number of vertices (k ≤ |U|)
When r = 1, each layer contains a singleton hyperedge {w_t}. Because layers are pairwise disjoint, distinct layers must contain distinct singletons, so the map t ↦ w_t is injective into the total vertex set U. Hence k ≤ |U|.
uses
Finset.card_eq_one,Finset.card_le_card_of_injOn,olb_mem_vs,Finset.disjoint_lefttheorem olb_one {V : Type*} [DecidableEq V] (F : OneLayeredFamily V 1) : F.k ≤ (olb_U F).card := by choose u hu using F.layers_nonempty have hc : ∀ t, (u t).card = 1 := fun t => F.layers_card t (u t) (hu t) choose w hw using fun t => Finset.card_eq_one.mp (hc t) calc F.k = (Finset.univ : Finset (Fin F.k)).card := by simp _ ≤ (olb_U F).card := Finset.card_le_card_of_injOn w (by intro t _ rw [Finset.mem_coe, olb_U, Finset.mem_biUnion] exact ⟨t, Finset.mem_univ _, (olb_mem_vs F t _).mpr ⟨u t, hu t, by rw [hw t]; exact Finset.mem_singleton_self _⟩⟩) (by intro s _ t _ hst by_contra hne have hus : u s = u t := by rw [hw s, hw t, hst] exact Finset.disjoint_left.mp (F.layers_disjoint s t hne) (hu s) (by rw [hus]; exact hu t))
The linear bound holds for r = 1
By induction on r with base case r = 1, setting r = 1 simplifies 2^(r-1) * r to 1 and 2^(r-1) * |U| + 1 to |U| + 1. The inequality k + 1 ≤ |U| + 1 reduces immediately to k ≤ |U|, proved in `olb_one`.
uses
Nat.le_induction,olb_onetheorem olb_main {V : Type*} [DecidableEq V] (r : ℕ) (hr : 1 ≤ r) : ∀ F : OneLayeredFamily V r, F.k + 2 ^ (r - 1) * r ≤ 2 ^ (r - 1) * (olb_U F).card + 1 := by induction r, hr using Nat.le_induction with | base => intro F have := olb_one F simp only [Nat.sub_self, pow_zero, one_mul] omega | succ r hr ih =>
Set up the induction step r → r + 1, identify the maximal layer l intersecting layer 0, and bound the link family on layers 0..l
For the induction step, strong induction on n = F.k proves a block bound involving the size of layer 0, |A_0|. We find the maximum layer index l such that layer l intersects A_0. Choosing a vertex v in their intersection, the interval property shows v is present in all layers 0..l. Forming the link family of v on these l + 1 layers yields a 1-layered family of r-subsets. The induction hypothesis on r gives a bound on l + 1, with vertex set bounded by |B_1| - 1 where B_1 is the union of the first l + 1 layers.
uses
Nat.strong_induction_on,Finset.not_disjoint_iff,olb_vs_mid,olb_link_U,Finset.card_erase_of_mem,Finset.card_le_cardhave block : ∀ n, ∀ F : OneLayeredFamily V (r + 1), F.k = n → F.k + 2 ^ (r - 1) * ((olb_vs F ⟨0, F.k_pos⟩).card + (r + 1)) ≤ 2 ^ (r - 1) * (2 * (olb_U F).card) + 1 := by intro n induction n using Nat.strong_induction_on with | _ n IH => intro F hFn have hc1 : 1 ≤ 2 ^ (r - 1) := Nat.one_le_two_pow have hA0 : (olb_vs F ⟨0, F.k_pos⟩).Nonempty := by obtain ⟨G, hG⟩ := F.layers_nonempty ⟨0, F.k_pos⟩ have := F.layers_card _ G hG obtain ⟨w, hw⟩ := Finset.card_pos.mp (by omega : 0 < G.card) exact ⟨w, (olb_mem_vs F _ w).mpr ⟨G, hG, hw⟩⟩ have ht0S : (⟨0, F.k_pos⟩ : Fin F.k) ∈ Finset.univ.filter (fun t : Fin F.k => ¬ Disjoint (olb_vs F t) (olb_vs F ⟨0, F.k_pos⟩)) := by simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.disjoint_self_iff_empty] exact hA0.ne_empty set l := (Finset.univ.filter (fun t : Fin F.k => ¬ Disjoint (olb_vs F t) (olb_vs F ⟨0, F.k_pos⟩))).max' ⟨_, ht0S⟩ with hl have hlS := Finset.max'_mem (Finset.univ.filter (fun t : Fin F.k => ¬ Disjoint (olb_vs F t) (olb_vs F ⟨0, F.k_pos⟩))) ⟨_, ht0S⟩ rw [← hl] at hlS have hmax : ∀ t, ¬ Disjoint (olb_vs F t) (olb_vs F ⟨0, F.k_pos⟩) → t ≤ l := fun t ht => Finset.le_max' _ t (by simp only [Finset.mem_filter, Finset.mem_univ, true_and]; exact ht) obtain ⟨v, hvl, hv0⟩ := Finset.not_disjoint_iff.mp (Finset.mem_filter.mp hlS).2 have hvall : ∀ t : Fin F.k, t.val < l.val + 1 → v ∈ olb_vs F t := fun t ht => olb_vs_mid F hv0 hvl (Fin.le_def.mpr (Nat.zero_le _)) (Fin.le_def.mpr (by omega)) have hlk : l.val + 1 ≤ F.k := l.isLt have hm0 : 0 < l.val + 1 := Nat.succ_pos _ have hG : (l.val + 1) + 2 ^ (r - 1) * r ≤ 2 ^ (r - 1) * (olb_U (r := r) (olb_link F v (l.val + 1) hm0 hlk hvall)).card + 1 := ih (olb_link F v (l.val + 1) hm0 hlk hvall) have hGk : (olb_link F v (l.val + 1) hm0 hlk hvall).k = l.val + 1 := rfl have hvB1 : v ∈ (Finset.univ.filter (fun t : Fin F.k => t.val < l.val + 1)).biUnion (olb_vs F) := by simp only [Finset.mem_biUnion, Finset.mem_filter, Finset.mem_univ, true_and] exact ⟨⟨0, F.k_pos⟩, Nat.succ_pos _, hv0⟩ have hGU0 := Finset.card_le_card (olb_link_U F v (l.val + 1) hm0 hlk hvall) rw [Finset.card_erase_of_mem hvB1] at hGU0 have hGU : (olb_U (r := r) (olb_link F v (l.val + 1) hm0 hlk hvall)).card ≤ ((Finset.univ.filter (fun t : Fin F.k => t.val < l.val + 1)).biUnion (olb_vs F)).card - 1 := hGU0 have hB1pos := Finset.card_pos.mpr ⟨v, hvB1⟩ have hAU : olb_vs F ⟨0, F.k_pos⟩ ⊆ olb_U F := fun w hw => by simp only [olb_U, Finset.mem_biUnion, Finset.mem_univ, true_and]; exact ⟨_, hw⟩ have hAB1 : olb_vs F ⟨0, F.k_pos⟩ ⊆ (Finset.univ.filter (fun t : Fin F.k => t.val < l.val + 1)).biUnion (olb_vs F) := fun w hw => by simp only [Finset.mem_biUnion, Finset.mem_filter, Finset.mem_univ, true_and] exact ⟨⟨0, F.k_pos⟩, Nat.succ_pos _, hw⟩
The block inequality holds in the case where layer 0 intersects the very last layer (l + 1 = F.k)
When l + 1 = F.k, all layers of the family are included in B_1, so B_1 = U. The bound from the link family together with `olb_ar1` immediately yields the desired inequality.
uses
olb_ar1,Finset.card_le_cardby_cases hend : l.val + 1 = F.k · have hB1eq : (Finset.univ.filter (fun t : Fin F.k => t.val < l.val + 1)).biUnion (olb_vs F) = olb_U F := by ext w simp only [olb_U, Finset.mem_biUnion, Finset.mem_filter, Finset.mem_univ, true_and] constructor · rintro ⟨t, -, ht⟩; exact ⟨t, ht⟩ · rintro ⟨t, ht⟩; exact ⟨t, by have := t.isLt; omega, ht⟩ rw [hB1eq] at hGU hB1pos have := olb_ar1 _ (l.val + 1) _ (olb_U F).card _ _ hG (by omega) (Finset.card_le_card hAU) rw [hend] at this exact this
The block inequality holds in the case l + 1 < F.k by splitting into prefix and suffix
When l + 1 < F.k, the suffix family starting at layer l + 1 has fewer than n layers, so the strong induction hypothesis applies to it. By maximality of l, layer 0 is disjoint from all layers in the suffix, so |A_0| + |V(suffix)| ≤ |U|. Moreover, any vertex in both the prefix union and suffix union must belong to layer l + 1 by the interval property, giving |B_1 ∩ V(suffix)| ≤ |olb_vs F (l + 1)|. Applying inclusion-exclusion and `olb_ar2` closes this branch.
uses
olb_suf_vs,olb_vs_mid,Finset.not_disjoint_iff,Finset.card_union_add_card_inter,Finset.card_union_of_disjoint,Finset.card_le_card,olb_ar2· have hj : l.val + 1 < F.k := by omega have hRk : (olb_suf F (l.val + 1) hj).k < n := by show F.k - (l.val + 1) < n omega have hR := IH _ hRk (olb_suf F (l.val + 1) hj) rfl have hA' : olb_vs (olb_suf F (l.val + 1) hj) ⟨0, (olb_suf F (l.val + 1) hj).k_pos⟩ = olb_vs F ⟨l.val + 1, hj⟩ := by rw [olb_suf_vs] congr 1 ext simp rw [hA'] at hR have hUR : olb_U (olb_suf F (l.val + 1) hj) ⊆ (Finset.univ.filter (fun t : Fin F.k => l.val + 1 ≤ t.val)).biUnion (olb_vs F) := by intro w hw simp only [olb_U, Finset.mem_biUnion, Finset.mem_univ, true_and] at hw obtain ⟨t, ht⟩ := hw rw [olb_suf_vs] at ht simp only [Finset.mem_biUnion, Finset.mem_filter, Finset.mem_univ, true_and] exact ⟨_, by simp only; omega, ht⟩ have hinter : (Finset.univ.filter (fun t : Fin F.k => t.val < l.val + 1)).biUnion (olb_vs F) ∩ (Finset.univ.filter (fun t : Fin F.k => l.val + 1 ≤ t.val)).biUnion (olb_vs F) ⊆ olb_vs F ⟨l.val + 1, hj⟩ := by intro w hw simp only [Finset.mem_inter, Finset.mem_biUnion, Finset.mem_filter, Finset.mem_univ, true_and] at hw obtain ⟨⟨s, hs, hws⟩, ⟨t, ht, hwt⟩⟩ := hw exact olb_vs_mid F hws hwt (Fin.le_def.mpr (by simp only; omega)) (Fin.le_def.mpr (by simp only; omega)) have hdisj : Disjoint (olb_vs F ⟨0, F.k_pos⟩) ((Finset.univ.filter (fun t : Fin F.k => l.val + 1 ≤ t.val)).biUnion (olb_vs F)) := by rw [Finset.disjoint_left] intro w hw0 hw simp only [Finset.mem_biUnion, Finset.mem_filter, Finset.mem_univ, true_and] at hw obtain ⟨t, ht, hwt⟩ := hw have := Fin.le_def.mp (hmax t (Finset.not_disjoint_iff.mpr ⟨w, hwt, hw0⟩)) omega have hR'U : (Finset.univ.filter (fun t : Fin F.k => l.val + 1 ≤ t.val)).biUnion (olb_vs F) ⊆ olb_U F := fun w hw => by simp only [Finset.mem_biUnion, Finset.mem_filter, Finset.mem_univ, true_and] at hw obtain ⟨t, -, hwt⟩ := hw simp only [olb_U, Finset.mem_biUnion, Finset.mem_univ, true_and]; exact ⟨t, hwt⟩ have hB1U : (Finset.univ.filter (fun t : Fin F.k => t.val < l.val + 1)).biUnion (olb_vs F) ⊆ olb_U F := fun w hw => by simp only [Finset.mem_biUnion, Finset.mem_filter, Finset.mem_univ, true_and] at hw obtain ⟨t, -, hwt⟩ := hw simp only [olb_U, Finset.mem_biUnion, Finset.mem_univ, true_and]; exact ⟨t, hwt⟩ have k1 := Finset.card_union_add_card_inter ((Finset.univ.filter (fun t : Fin F.k => t.val < l.val + 1)).biUnion (olb_vs F)) ((Finset.univ.filter (fun t : Fin F.k => l.val + 1 ≤ t.val)).biUnion (olb_vs F)) have k2 := Finset.card_le_card (Finset.union_subset hB1U hR'U) have k3 := Finset.card_le_card hinter have k4 := Finset.card_union_of_disjoint hdisj have k5 := Finset.card_le_card (Finset.union_subset hAU hR'U) have k6 := Finset.card_le_card hUR have hRk' : (olb_suf F (l.val + 1) hj).k = F.k - (l.val + 1) := rfl rw [hRk'] at hR exact olb_ar2 (k := F.k) (U := (olb_U F).card) (n1 := ((Finset.univ.filter (fun t : Fin F.k => t.val < l.val + 1)).biUnion (olb_vs F)).card) (R := ((Finset.univ.filter (fun t : Fin F.k => l.val + 1 ≤ t.val)).biUnion (olb_vs F)).card) _ (l.val + 1) (F.k - (l.val + 1)) _ _ _ _ _ hc1 hr (by omega) hG (by omega) hR k6 (by omega) (by omega)
Deduce the main inequality for r + 1 from the block inequality
Since layer 0 contains at least one hyperedge of size r + 1, its vertex set satisfies r + 1 ≤ |A_0|. Substituting this into the block bound and factoring 2^(r+1-1) = 2 * 2^(r-1) finishes the inductive step for `olb_main`.
uses
pow_succ',Nat.mul_le_mul_left,Finset.card_le_cardintro F have hb := block _ F rfl have ha : r + 1 ≤ (olb_vs F ⟨0, F.k_pos⟩).card := by obtain ⟨G, hG⟩ := F.layers_nonempty ⟨0, F.k_pos⟩ calc r + 1 = G.card := (F.layers_card _ G hG).symm _ ≤ _ := Finset.card_le_card (fun w hw => (olb_mem_vs F _ w).mpr ⟨G, hG, hw⟩) have hp : 2 ^ (r + 1 - 1) = 2 * 2 ^ (r - 1) := by rw [Nat.add_sub_cancel, ← pow_succ'] congr 1 omega rw [hp] have m := Nat.mul_le_mul_left (2 ^ (r - 1)) ha nlinarith
Maximum number of layers on at most m vertices satisfies F(m, r) ≤ 2^(r - 1) * (m - r) + 1
Taking the supremum over all 1-layered families on at most m vertices, each such family has total vertex count |U| ≤ m and |U| ≥ r. Applying `olb_main` and the monotonic inequality 2^(r-1) * |U| ≤ 2^(r-1) * (m - r) + 2^(r-1) * r completes the proof.
uses
csSup_le',olb_main,Finset.card_le_univ,Finset.card_le_card/-- The linear upper bound F(m, r) ≤ 2^(r-1)(m-r) + 1. -/ theorem one_layered_linear_bound (m r : ℕ) (hr : 1 ≤ r) (hm : r ≤ m) : one_layered_max_layers m r ≤ 2 ^ (r - 1) * (m - r) + 1 := by unfold one_layered_max_layers refine csSup_le' ?_ rintro k ⟨n, hn, F, rfl⟩ have h := olb_main r hr F have hU : (olb_U F).card ≤ m := (Finset.card_le_univ _).trans (by simp [hn]) have hrU : r ≤ (olb_U F).card := by obtain ⟨G, hG⟩ := F.layers_nonempty ⟨0, F.k_pos⟩ refine (F.layers_card _ G hG).symm.le.trans (Finset.card_le_card (fun w hw => ?_)) simp only [olb_U, Finset.mem_biUnion, Finset.mem_univ, true_and] exact ⟨⟨0, F.k_pos⟩, (olb_mem_vs F _ w).mpr ⟨G, hG, hw⟩⟩ have e : 2 ^ (r - 1) * (olb_U F).card ≤ 2 ^ (r - 1) * (m - r) + 2 ^ (r - 1) * r := by rw [← Nat.mul_add]; exact Nat.mul_le_mul_left _ (by omega) omega
olb_vs- the vertex set of layer t in a family F, defined as the union of all hyperedges in layer t
Finset.singleton_nonempty- the singleton set {a} is non-empty
olb_mem_vs- a vertex belongs to layer t if and only if it belongs to some hyperedge in layer t
Finset.singleton_subset_iff- the singleton {a} is a subset of s if and only if a belongs to s
Fin.ext- two elements of Fin n are equal if and only if their underlying natural numbers are equal
Fin.le_def- inequality between elements of Fin n is equivalent to inequality of their underlying natural numbers
olb_suf- the suffix sub-family obtained by dropping the first j layers of a 1-layered family
Finset.card_erase_of_mem- erasing an element from a finite set decreases its cardinality by 1
Finset.insert_erase- re-inserting an element into a set from which it was erased recovers the original set
Finset.disjoint_left- two sets are disjoint if and only if no element of the first belongs to the second
Finset.insert_nonempty- inserting an element into any set produces a non-empty set
Finset.insert_subset- inserting an element preserves subset inclusion if the element and the original set are both contained in the target
Finset.erase_subset- erasing an element produces a subset of the original set
Nat.mul_le_mul_left- multiplying an inequality of natural numbers by a non-negative factor preserves the inequality
Nat.mul_le_mul- multiplying two inequalities between natural numbers preserves the inequality
Finset.card_eq_one- a finite set has cardinality 1 if and only if it is a singleton
Finset.card_le_card_of_injOn- an injective map from a finite set into another implies the domain's cardinality is at most the codomain's
olb_one- in any 1-layered family of 1-subsets, the number of layers is at most the total number of vertices (k ≤ |U|)
Nat.le_induction- induction principle for natural numbers starting from a base value
Nat.strong_induction_on- strong induction principle on natural numbers
Finset.not_disjoint_iff- two sets are not disjoint if and only if they share an element
olb_vs_mid- if a vertex appears in layer s and layer t with s ≤ u ≤ t, then it appears in layer u
Finset.card_le_card- subset inclusion implies inequality of finite cardinalities
olb_link_U- the total vertex set of the link family of v on the first m layers is contained in the union of those layers minus {v}
olb_ar1- linear arithmetic inequality bounding k + c*(a + r + 1) in the terminal case l + 1 = k
olb_suf_vs- the vertex set of layer t in the suffix family corresponds to layer t + j in the original family
Finset.card_union_add_card_inter- inclusion-exclusion formula for two finite sets: |s ∪ t| + |s ∩ t| = |s| + |t|
Finset.card_union_of_disjoint- the cardinality of the union of two disjoint finite sets is the sum of their cardinalities
olb_ar2- arithmetic inequality combining the prefix link bound and suffix strong induction bound
pow_succ'- successor identity for powers: a^(n + 1) = a * a^n
csSup_le'- if an element is an upper bound for a set, it is at least the supremum of the set
olb_main- every 1-layered family of r-subsets satisfies k + 2^(r-1)*r ≤ 2^(r-1)*|U| + 1
Finset.card_le_univ- the cardinality of a sub-finset of a type is at most the cardinality of the universe type
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.
def olb_vs {V : Type*} [DecidableEq V] {r : ℕ} (F : OneLayeredFamily V r) (t : Fin F.k) : Finset V := (F.layers t).biUnion iddef olb_U {V : Type*} [DecidableEq V] {r : ℕ} (F : OneLayeredFamily V r) : Finset V := (Finset.univ : Finset (Fin F.k)).biUnion (olb_vs F)theorem olb_mem_vs {V : Type*} [DecidableEq V] {r : ℕ} (F : OneLayeredFamily V r) (t : Fin F.k) (w : V) : w ∈ olb_vs F t ↔ ∃ G ∈ F.layers t, w ∈ G := by simp [olb_vs]theorem olb_vs_mid {V : Type*} [DecidableEq V] {r : ℕ} (F : OneLayeredFamily V r) {w : V} {s t u : Fin F.k} (hs : w ∈ olb_vs F s) (ht : w ∈ olb_vs F t) (h1 : s ≤ u) (h2 : u ≤ t) : w ∈ olb_vs F u := by have h := (F.interval_property {w} (Finset.singleton_nonempty w)).out rw [olb_mem_vs] at hs ht ⊢ obtain ⟨G1, hG1, hw1⟩ := hs obtain ⟨G2, hG2, hw2⟩ := ht obtain ⟨G, hG, hsub⟩ := h (x := s) ⟨G1, hG1, Finset.singleton_subset_iff.mpr hw1⟩ (y := t) ⟨G2, hG2, Finset.singleton_subset_iff.mpr hw2⟩ ⟨h1, h2⟩ exact ⟨G, hG, Finset.singleton_subset_iff.mp hsub⟩def olb_suf {V : Type*} [DecidableEq V] {r : ℕ} (F : OneLayeredFamily V r) (j : ℕ) (hj : j < F.k) : OneLayeredFamily V r where k := F.k - j k_pos := by omega layers t := F.layers ⟨t.val + j, by have := t.isLt; omega⟩ layers_nonempty t := F.layers_nonempty _ layers_card t := F.layers_card _ layers_disjoint t₁ t₂ h := F.layers_disjoint _ _ (fun e => h (Fin.ext (by have := congrArg Fin.val e; simp only at this; omega))) interval_property S hS := by have h := (F.interval_property S hS).out refine ⟨fun x hx y hy z hz => ?_⟩ have hz1 := Fin.le_def.mp hz.1 have hz2 := Fin.le_def.mp hz.2 exact h (x := ⟨x.val + j, by have := x.isLt; omega⟩) hx (y := ⟨y.val + j, by have := y.isLt; omega⟩) hy ⟨Fin.mk_le_mk.mpr (by omega), Fin.mk_le_mk.mpr (by omega)⟩theorem olb_suf_vs {V : Type*} [DecidableEq V] {r : ℕ} (F : OneLayeredFamily V r) (j : ℕ) (hj : j < F.k) (t : Fin (olb_suf F j hj).k) : olb_vs (olb_suf F j hj) t = olb_vs F ⟨t.val + j, by have := t.isLt; simp [olb_suf] at this; omega⟩ := rfldef olb_link {V : Type*} [DecidableEq V] {r : ℕ} (F : OneLayeredFamily V r) (v : V) (m : ℕ) (hm0 : 0 < m) (hm : m ≤ F.k) (hv : ∀ t : Fin F.k, t.val < m → v ∈ olb_vs F t) : OneLayeredFamily V (r - 1) where k := m k_pos := hm0 layers t := ((F.layers ⟨t.val, by omega⟩).filter (fun G => v ∈ G)).image (fun G => G.erase v) layers_nonempty t := by obtain ⟨G, hG, hv'⟩ := (olb_mem_vs F _ v).mp (hv ⟨t.val, by omega⟩ t.isLt) exact ⟨G.erase v, Finset.mem_image.mpr ⟨G, Finset.mem_filter.mpr ⟨hG, hv'⟩, rfl⟩⟩ layers_card t G hG := by obtain ⟨G', hG', rfl⟩ := Finset.mem_image.mp hG rw [Finset.mem_filter] at hG' rw [Finset.card_erase_of_mem hG'.2, F.layers_card _ _ hG'.1] layers_disjoint t₁ t₂ h := by rw [Finset.disjoint_left] intro G h1 h2 obtain ⟨G1, hG1, rfl⟩ := Finset.mem_image.mp h1 obtain ⟨G2, hG2, he⟩ := Finset.mem_image.mp h2 rw [Finset.mem_filter] at hG1 hG2 have : G2 = G1 := by rw [← Finset.insert_erase hG1.2, ← Finset.insert_erase hG2.2, he] subst this exact Finset.disjoint_left.mp (F.layers_disjoint _ _ (fun e => h (Fin.ext (by have := congrArg Fin.val e; simp only at this; omega)))) hG1.1 hG2.1 interval_property S hS := by refine ⟨fun x hx y hy z hz => ?_⟩ obtain ⟨G1, hG1, hS1⟩ := hx obtain ⟨G2, hG2, hS2⟩ := hy obtain ⟨H1, hH1, rfl⟩ := Finset.mem_image.mp hG1 obtain ⟨H2, hH2, rfl⟩ := Finset.mem_image.mp hG2 rw [Finset.mem_filter] at hH1 hH2 have hvS : v ∉ S := fun h => Finset.notMem_erase v H1 (hS1 h) have h := (F.interval_property (insert v S) (Finset.insert_nonempty v S)).out have hz1 := Fin.le_def.mp hz.1 have hz2 := Fin.le_def.mp hz.2 have hxl : x.val < F.k := by have := x.isLt; omega have hyl : y.val < F.k := by have := y.isLt; omega have hzl : z.val < F.k := by have := z.isLt; omega have hx' : (⟨x.val, hxl⟩ : Fin F.k) ∈ {t : Fin F.k | ∃ G ∈ F.layers t, insert v S ⊆ G} := ⟨H1, hH1.1, Finset.insert_subset hH1.2 (hS1.trans (Finset.erase_subset v H1))⟩ have hy' : (⟨y.val, hyl⟩ : Fin F.k) ∈ {t : Fin F.k | ∃ G ∈ F.layers t, insert v S ⊆ G} := ⟨H2, hH2.1, Finset.insert_subset hH2.2 (hS2.trans (Finset.erase_subset v H2))⟩ have hzm : (⟨z.val, hzl⟩ : Fin F.k) ∈ Set.Icc (⟨x.val, hxl⟩ : Fin F.k) ⟨y.val, hyl⟩ := ⟨Fin.mk_le_mk.mpr hz1, Fin.mk_le_mk.mpr hz2⟩ obtain ⟨H3, hH3, hS3⟩ := h hx' hy' hzm refine ⟨H3.erase v, Finset.mem_image.mpr ⟨H3, Finset.mem_filter.mpr ⟨hH3, hS3 (Finset.mem_insert_self v S)⟩, rfl⟩, ?_⟩ intro w hw exact Finset.mem_erase.mpr ⟨fun e => hvS (e ▸ hw), hS3 (Finset.mem_insert_of_mem hw)⟩theorem olb_link_U {V : Type*} [DecidableEq V] {r : ℕ} (F : OneLayeredFamily V r) (v : V) (m : ℕ) (hm0 : 0 < m) (hm : m ≤ F.k) (hv : ∀ t : Fin F.k, t.val < m → v ∈ olb_vs F t) : olb_U (olb_link F v m hm0 hm hv) ⊆ ((Finset.univ.filter (fun t : Fin F.k => t.val < m)).biUnion (olb_vs F)).erase v := by intro w hw simp only [olb_U, Finset.mem_biUnion, Finset.mem_univ, true_and, olb_vs, id] at hw obtain ⟨t, G, hG, hwG⟩ := hw obtain ⟨H, hH, rfl⟩ := Finset.mem_image.mp hG rw [Finset.mem_filter] at hH rw [Finset.mem_erase] at hwG refine Finset.mem_erase.mpr ⟨hwG.1, ?_⟩ simp only [Finset.mem_biUnion, Finset.mem_filter, Finset.mem_univ, true_and] exact ⟨⟨t.val, by have : t.val < m := t.isLt; omega⟩, t.isLt, (olb_mem_vs F _ w).mpr ⟨H, hH.1, hwG.2⟩⟩theorem olb_ar1 (c k a U r g : ℕ) (hG : k + c * r ≤ c * g + 1) (hg : g + 1 ≤ U) (ha : a ≤ U) : k + c * (a + (r + 1)) ≤ c * (2 * U) + 1 := by have h1 : c * (g + 1) ≤ c * U := Nat.mul_le_mul_left c hg have h2 : c * a ≤ c * U := Nat.mul_le_mul_left c ha nlinariththeorem olb_ar2 (c k l1 d a U r g n1 a' R uR : ℕ) (hc : 1 ≤ c) (hr : 1 ≤ r) (hk : k = l1 + d) (hG : l1 + c * r ≤ c * g + 1) (hg : g + 1 ≤ n1) (hR : d + c * (a' + (r + 1)) ≤ c * (2 * uR) + 1) (huR : uR ≤ R) (h3 : n1 + R ≤ U + a') (h4 : a + R ≤ U) : k + c * (a + (r + 1)) ≤ c * (2 * U) + 1 := by have m1 : c * (g + 1) ≤ c * n1 := Nat.mul_le_mul_left c hg have m2 : c * uR ≤ c * R := Nat.mul_le_mul_left c huR have m3 : c * (n1 + R) ≤ c * (U + a') := Nat.mul_le_mul_left c h3 have m4 : c * (a + R) ≤ c * U := Nat.mul_le_mul_left c h4 have m5 : 1 * 2 ≤ c * (r + 1) := Nat.mul_le_mul hc (by omega) subst hk nlinariththeorem olb_one {V : Type*} [DecidableEq V] (F : OneLayeredFamily V 1) : F.k ≤ (olb_U F).card := by choose u hu using F.layers_nonempty have hc : ∀ t, (u t).card = 1 := fun t => F.layers_card t (u t) (hu t) choose w hw using fun t => Finset.card_eq_one.mp (hc t) calc F.k = (Finset.univ : Finset (Fin F.k)).card := by simp _ ≤ (olb_U F).card := Finset.card_le_card_of_injOn w (by intro t _ rw [Finset.mem_coe, olb_U, Finset.mem_biUnion] exact ⟨t, Finset.mem_univ _, (olb_mem_vs F t _).mpr ⟨u t, hu t, by rw [hw t]; exact Finset.mem_singleton_self _⟩⟩) (by intro s _ t _ hst by_contra hne have hus : u s = u t := by rw [hw s, hw t, hst] exact Finset.disjoint_left.mp (F.layers_disjoint s t hne) (hu s) (by rw [hus]; exact hu t))theorem olb_main {V : Type*} [DecidableEq V] (r : ℕ) (hr : 1 ≤ r) : ∀ F : OneLayeredFamily V r, F.k + 2 ^ (r - 1) * r ≤ 2 ^ (r - 1) * (olb_U F).card + 1 := by induction r, hr using Nat.le_induction with | base => intro F have := olb_one F simp only [Nat.sub_self, pow_zero, one_mul] omega | succ r hr ih => have block : ∀ n, ∀ F : OneLayeredFamily V (r + 1), F.k = n → F.k + 2 ^ (r - 1) * ((olb_vs F ⟨0, F.k_pos⟩).card + (r + 1)) ≤ 2 ^ (r - 1) * (2 * (olb_U F).card) + 1 := by intro n induction n using Nat.strong_induction_on with | _ n IH => intro F hFn have hc1 : 1 ≤ 2 ^ (r - 1) := Nat.one_le_two_pow have hA0 : (olb_vs F ⟨0, F.k_pos⟩).Nonempty := by obtain ⟨G, hG⟩ := F.layers_nonempty ⟨0, F.k_pos⟩ have := F.layers_card _ G hG obtain ⟨w, hw⟩ := Finset.card_pos.mp (by omega : 0 < G.card) exact ⟨w, (olb_mem_vs F _ w).mpr ⟨G, hG, hw⟩⟩ have ht0S : (⟨0, F.k_pos⟩ : Fin F.k) ∈ Finset.univ.filter (fun t : Fin F.k => ¬ Disjoint (olb_vs F t) (olb_vs F ⟨0, F.k_pos⟩)) := by simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.disjoint_self_iff_empty] exact hA0.ne_empty set l := (Finset.univ.filter (fun t : Fin F.k => ¬ Disjoint (olb_vs F t) (olb_vs F ⟨0, F.k_pos⟩))).max' ⟨_, ht0S⟩ with hl have hlS := Finset.max'_mem (Finset.univ.filter (fun t : Fin F.k => ¬ Disjoint (olb_vs F t) (olb_vs F ⟨0, F.k_pos⟩))) ⟨_, ht0S⟩ rw [← hl] at hlS have hmax : ∀ t, ¬ Disjoint (olb_vs F t) (olb_vs F ⟨0, F.k_pos⟩) → t ≤ l := fun t ht => Finset.le_max' _ t (by simp only [Finset.mem_filter, Finset.mem_univ, true_and]; exact ht) obtain ⟨v, hvl, hv0⟩ := Finset.not_disjoint_iff.mp (Finset.mem_filter.mp hlS).2 have hvall : ∀ t : Fin F.k, t.val < l.val + 1 → v ∈ olb_vs F t := fun t ht => olb_vs_mid F hv0 hvl (Fin.le_def.mpr (Nat.zero_le _)) (Fin.le_def.mpr (by omega)) have hlk : l.val + 1 ≤ F.k := l.isLt have hm0 : 0 < l.val + 1 := Nat.succ_pos _ have hG : (l.val + 1) + 2 ^ (r - 1) * r ≤ 2 ^ (r - 1) * (olb_U (r := r) (olb_link F v (l.val + 1) hm0 hlk hvall)).card + 1 := ih (olb_link F v (l.val + 1) hm0 hlk hvall) have hGk : (olb_link F v (l.val + 1) hm0 hlk hvall).k = l.val + 1 := rfl have hvB1 : v ∈ (Finset.univ.filter (fun t : Fin F.k => t.val < l.val + 1)).biUnion (olb_vs F) := by simp only [Finset.mem_biUnion, Finset.mem_filter, Finset.mem_univ, true_and] exact ⟨⟨0, F.k_pos⟩, Nat.succ_pos _, hv0⟩ have hGU0 := Finset.card_le_card (olb_link_U F v (l.val + 1) hm0 hlk hvall) rw [Finset.card_erase_of_mem hvB1] at hGU0 have hGU : (olb_U (r := r) (olb_link F v (l.val + 1) hm0 hlk hvall)).card ≤ ((Finset.univ.filter (fun t : Fin F.k => t.val < l.val + 1)).biUnion (olb_vs F)).card - 1 := hGU0 have hB1pos := Finset.card_pos.mpr ⟨v, hvB1⟩ have hAU : olb_vs F ⟨0, F.k_pos⟩ ⊆ olb_U F := fun w hw => by simp only [olb_U, Finset.mem_biUnion, Finset.mem_univ, true_and]; exact ⟨_, hw⟩ have hAB1 : olb_vs F ⟨0, F.k_pos⟩ ⊆ (Finset.univ.filter (fun t : Fin F.k => t.val < l.val + 1)).biUnion (olb_vs F) := fun w hw => by simp only [Finset.mem_biUnion, Finset.mem_filter, Finset.mem_univ, true_and] exact ⟨⟨0, F.k_pos⟩, Nat.succ_pos _, hw⟩ by_cases hend : l.val + 1 = F.k · have hB1eq : (Finset.univ.filter (fun t : Fin F.k => t.val < l.val + 1)).biUnion (olb_vs F) = olb_U F := by ext w simp only [olb_U, Finset.mem_biUnion, Finset.mem_filter, Finset.mem_univ, true_and] constructor · rintro ⟨t, -, ht⟩; exact ⟨t, ht⟩ · rintro ⟨t, ht⟩; exact ⟨t, by have := t.isLt; omega, ht⟩ rw [hB1eq] at hGU hB1pos have := olb_ar1 _ (l.val + 1) _ (olb_U F).card _ _ hG (by omega) (Finset.card_le_card hAU) rw [hend] at this exact this · have hj : l.val + 1 < F.k := by omega have hRk : (olb_suf F (l.val + 1) hj).k < n := by show F.k - (l.val + 1) < n omega have hR := IH _ hRk (olb_suf F (l.val + 1) hj) rfl have hA' : olb_vs (olb_suf F (l.val + 1) hj) ⟨0, (olb_suf F (l.val + 1) hj).k_pos⟩ = olb_vs F ⟨l.val + 1, hj⟩ := by rw [olb_suf_vs] congr 1 ext simp rw [hA'] at hR have hUR : olb_U (olb_suf F (l.val + 1) hj) ⊆ (Finset.univ.filter (fun t : Fin F.k => l.val + 1 ≤ t.val)).biUnion (olb_vs F) := by intro w hw simp only [olb_U, Finset.mem_biUnion, Finset.mem_univ, true_and] at hw obtain ⟨t, ht⟩ := hw rw [olb_suf_vs] at ht simp only [Finset.mem_biUnion, Finset.mem_filter, Finset.mem_univ, true_and] exact ⟨_, by simp only; omega, ht⟩ have hinter : (Finset.univ.filter (fun t : Fin F.k => t.val < l.val + 1)).biUnion (olb_vs F) ∩ (Finset.univ.filter (fun t : Fin F.k => l.val + 1 ≤ t.val)).biUnion (olb_vs F) ⊆ olb_vs F ⟨l.val + 1, hj⟩ := by intro w hw simp only [Finset.mem_inter, Finset.mem_biUnion, Finset.mem_filter, Finset.mem_univ, true_and] at hw obtain ⟨⟨s, hs, hws⟩, ⟨t, ht, hwt⟩⟩ := hw exact olb_vs_mid F hws hwt (Fin.le_def.mpr (by simp only; omega)) (Fin.le_def.mpr (by simp only; omega)) have hdisj : Disjoint (olb_vs F ⟨0, F.k_pos⟩) ((Finset.univ.filter (fun t : Fin F.k => l.val + 1 ≤ t.val)).biUnion (olb_vs F)) := by rw [Finset.disjoint_left] intro w hw0 hw simp only [Finset.mem_biUnion, Finset.mem_filter, Finset.mem_univ, true_and] at hw obtain ⟨t, ht, hwt⟩ := hw have := Fin.le_def.mp (hmax t (Finset.not_disjoint_iff.mpr ⟨w, hwt, hw0⟩)) omega have hR'U : (Finset.univ.filter (fun t : Fin F.k => l.val + 1 ≤ t.val)).biUnion (olb_vs F) ⊆ olb_U F := fun w hw => by simp only [Finset.mem_biUnion, Finset.mem_filter, Finset.mem_univ, true_and] at hw obtain ⟨t, -, hwt⟩ := hw simp only [olb_U, Finset.mem_biUnion, Finset.mem_univ, true_and]; exact ⟨t, hwt⟩ have hB1U : (Finset.univ.filter (fun t : Fin F.k => t.val < l.val + 1)).biUnion (olb_vs F) ⊆ olb_U F := fun w hw => by simp only [Finset.mem_biUnion, Finset.mem_filter, Finset.mem_univ, true_and] at hw obtain ⟨t, -, hwt⟩ := hw simp only [olb_U, Finset.mem_biUnion, Finset.mem_univ, true_and]; exact ⟨t, hwt⟩ have k1 := Finset.card_union_add_card_inter ((Finset.univ.filter (fun t : Fin F.k => t.val < l.val + 1)).biUnion (olb_vs F)) ((Finset.univ.filter (fun t : Fin F.k => l.val + 1 ≤ t.val)).biUnion (olb_vs F)) have k2 := Finset.card_le_card (Finset.union_subset hB1U hR'U) have k3 := Finset.card_le_card hinter have k4 := Finset.card_union_of_disjoint hdisj have k5 := Finset.card_le_card (Finset.union_subset hAU hR'U) have k6 := Finset.card_le_card hUR have hRk' : (olb_suf F (l.val + 1) hj).k = F.k - (l.val + 1) := rfl rw [hRk'] at hR exact olb_ar2 (k := F.k) (U := (olb_U F).card) (n1 := ((Finset.univ.filter (fun t : Fin F.k => t.val < l.val + 1)).biUnion (olb_vs F)).card) (R := ((Finset.univ.filter (fun t : Fin F.k => l.val + 1 ≤ t.val)).biUnion (olb_vs F)).card) _ (l.val + 1) (F.k - (l.val + 1)) _ _ _ _ _ hc1 hr (by omega) hG (by omega) hR k6 (by omega) (by omega) intro F have hb := block _ F rfl have ha : r + 1 ≤ (olb_vs F ⟨0, F.k_pos⟩).card := by obtain ⟨G, hG⟩ := F.layers_nonempty ⟨0, F.k_pos⟩ calc r + 1 = G.card := (F.layers_card _ G hG).symm _ ≤ _ := Finset.card_le_card (fun w hw => (olb_mem_vs F _ w).mpr ⟨G, hG, hw⟩) have hp : 2 ^ (r + 1 - 1) = 2 * 2 ^ (r - 1) := by rw [Nat.add_sub_cancel, ← pow_succ'] congr 1 omega rw [hp] have m := Nat.mul_le_mul_left (2 ^ (r - 1)) ha nlinarith/-- The linear upper bound F(m, r) ≤ 2^(r-1)(m-r) + 1. -/theorem one_layered_linear_bound (m r : ℕ) (hr : 1 ≤ r) (hm : r ≤ m) : one_layered_max_layers m r ≤ 2 ^ (r - 1) * (m - r) + 1 := by unfold one_layered_max_layers refine csSup_le' ?_ rintro k ⟨n, hn, F, rfl⟩ have h := olb_main r hr F have hU : (olb_U F).card ≤ m := (Finset.card_le_univ _).trans (by simp [hn]) have hrU : r ≤ (olb_U F).card := by obtain ⟨G, hG⟩ := F.layers_nonempty ⟨0, F.k_pos⟩ refine (F.layers_card _ G hG).symm.le.trans (Finset.card_le_card (fun w hw => ?_)) simp only [olb_U, Finset.mem_biUnion, Finset.mem_univ, true_and] exact ⟨⟨0, F.k_pos⟩, (olb_mem_vs F _ w).mpr ⟨G, hG, hw⟩⟩ have e : 2 ^ (r - 1) * (olb_U F).card ≤ 2 ^ (r - 1) * (m - r) + 2 ^ (r - 1) * r := by rw [← Nat.mul_add]; exact Nat.mul_le_mul_left _ (by omega) omega