one_layered_family_upper_bounds
For 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 F(m, r) ≤ 2^(r - 1) * (m - r) + 1 and F(m, r) ≤ (m - r + 1) * Nat.choose (Nat.log 2 (m - r + 1) + r - 1) (r - 1), and this binomial bound is at most (m - r + 1)^(1 + Real.log r / Real.log 2).
Statement
theorem one_layered_family_upper_bounds (m r : ℕ) (hr : 1 ≤ r) (hm : r ≤ m) :
one_layered_max_layers m r ≤ 2 ^ (r - 1) * (m - r) + 1 ∧
one_layered_max_layers m r ≤ (m - r + 1) * Nat.choose (Nat.log 2 (m - r + 1) + r - 1) (r - 1) ∧
((m - r + 1 : ℝ) * ((Nat.log 2 (m - r + 1) + r - 1).choose (r - 1) : ℝ)) ≤
(m - r + 1 : ℝ) ^ (1 + Real.log (r : ℝ) / Real.log 2)- Formalizes
- arXiv:2611.08071 Theorem 2.1
- Verified
- 09 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…
- one_layered_linear_boundFor 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…
- one_layered_binomial_boundFor 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…
- one_layered_binomial_bound_le_powerFor integers r ≥ 1 and m ≥ r, the binomial bound (m - r + 1) * choose(⌊log_2(m - r + 1)⌋ + r - 1, r - 1) is at most (m - r + 1)^(1 + log_2…
Read back from the Lean
For all natural numbers $m$ and $r$ satisfying $1 \le r$ and $r \le m$, the following three inequalities hold simultaneously: 1. $\text{one\_layered\_max\_layers}(m, r) \le 2^{r-1}(m - r) + 1$; 2. $\text{one\_layered\_max\_layers}(m, r) \le (m - r + 1) \dbinom{\lfloor \log_2(m - r + 1) \rfloor + r - 1}{r - 1}$; 3. When cast to the real numbers $\mathbb{R}$, $$(m - r + 1) \dbinom{\lfloor \log_2(m - r + 1) \rfloor + r - 1}{r - 1} \le (m - r + 1)^{1 + \frac{\ln r}{\ln 2}}.$$ Here, $\text{one\_layered\_max\_layers}(m, r)$ is the supremum (in $\mathbb{N}$) of the set of all integers $k$ such that there exists some $n \le m$ and a one-layered family $F$ of $r$-element subsets over the ground set $\text{Fin } n$ having $k$ layers. A one-layered family consists of: - an integer $k > 0$; - $k$ layers (indexed by $t \in \text{Fin } k$), each being a non-empty family of $r$-element subsets of $\text{Fin } n$; - pairwise disjoint layers (no $r$-set appears in multiple layers); - the interval property: for every non-empty subset $S \subseteq \text{Fin } n$, the set of layer indices $\{t \in \text{Fin } k \mid \exists F \in \text{layers } t, S \subseteq F\}$ is order-connected (an interval) in $\text{Fin } k$.
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 collects three upper bounds on the maximum number of layers in a 1-layered family into a single conjunction: a linear bound, a binomial bound, and an exponentiated bound on the binomial quantity. The proof simply packages together three previously established lemmas, one for each conjunct.
All three bounds—linear, binomial, and power upper bound—hold simultaneously.
The goal is a conjunction of three inequalities. The proof constructs the conjunction directly by supplying the proofs from three previously established theorems: `one_layered_linear_bound`, `one_layered_binomial_bound`, and `one_layered_binomial_bound_le_power`, each applied to m, r, and the hypotheses 1 ≤ r and r ≤ m.
uses
one_layered_linear_bound,one_layered_binomial_bound,one_layered_binomial_bound_le_powerexact ⟨one_layered_linear_bound m r hr hm, one_layered_binomial_bound m r hr hm, one_layered_binomial_bound_le_power m r hr hm⟩
one_layered_linear_bound- For integers r ≥ 1 and m ≥ r, the maximum number of layers of a 1-layered family on at most m vertices satisfies F(m, r) ≤ 2^(r - 1) * (m - r) + 1.
one_layered_binomial_bound- For integers r ≥ 1 and m ≥ r, the maximum number of layers satisfies F(m, r) ≤ (m - r + 1) * ((⌊log₂ (m - r + 1)⌋ + r - 1) choose (r - 1)).
one_layered_binomial_bound_le_power- For integers r ≥ 1 and m ≥ r, the binomial bound (m - r + 1) * ((⌊log₂ (m - r + 1)⌋ + r - 1) choose (r - 1)) is bounded above by (m - r + 1)^(1 + log r / log 2).
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.
/-- Upper bounds on the number of layers in 1-layered families (Theorem 2.1 of arXiv:2611.08071). -/theorem one_layered_family_upper_bounds (m r : ℕ) (hr : 1 ≤ r) (hm : r ≤ m) : one_layered_max_layers m r ≤ 2 ^ (r - 1) * (m - r) + 1 ∧ one_layered_max_layers m r ≤ (m - r + 1) * Nat.choose (Nat.log 2 (m - r + 1) + r - 1) (r - 1) ∧ ((m - r + 1 : ℝ) * ((Nat.log 2 (m - r + 1) + r - 1).choose (r - 1) : ℝ)) ≤ (m - r + 1 : ℝ) ^ (1 + Real.log (r : ℝ) / Real.log 2) := by exact ⟨one_layered_linear_bound m r hr hm, one_layered_binomial_bound m r hr hm, one_layered_binomial_bound_le_power m r hr hm⟩