The Lubell–Yamamoto–Meshalkin (LYM) inequality
ProvedFamousTheorems.lym_inequalityThe LYM inequality. Let be a finite set with and an antichain of subsets of (no member contains another). If is the number of members of of size , then
Since , it gives Sperner's theorem immediately: an antichain in has at most members. The Lubell–Yamamoto–Meshalkin inequality is a model for counting arguments with chains in extremal set theory.
Formalization note. Mathlib's Finset.lubell_yamamoto_meshalkin_inequality_sum_card_div_choose, specialised to rational coefficients. 𝒜.slice r is the subfamily of members of size , and IsAntichain (· ⊆ ·) is the antichain condition.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem lym_inequality {α : Type*} [Fintype α] {𝒜 : Finset (Finset α)} (h𝒜 : IsAntichain (· ⊆ ·) (𝒜 : Set (Finset α))) :
∑ r ∈ Finset.range (Fintype.card α + 1), ((𝒜.slice r).card / (Fintype.card α).choose r : ℚ) ≤ 1 := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `Finset.lubell_yamamoto_meshalkin_inequality_sum_card_div_choose`. Proof here reduces to that Mathlib result.