TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-07-31

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Lubell-Yamamoto-Meshalkin inequality for antichains in a Boolean lattice

Statement

Let $A$ be an $n$ -element set and let $F \subseteq P (A)$ be an antichain. Then

$\sum_{S \in F} \frac{1}{(\binom{n}{∣ S ∣})} \leq 1.$

Facts & Assumptions

Given: An $n$ -element set $A$ and an antichain $F$ in its Boolean lattice.

[L1]

There are $n!$ maximal chains in $B (A)$ , and a fixed $k$ -set belongs to exactly $k! (n - k)!$ of them (The Boolean lattice on an $n$ -element set has $n!$ maximal chains, and exactly $k! (n - k)!$ contain a fixed $k$ -set).

[F1]

An antichain contains no two comparable distinct elements (Antichains, chain covers, and antichain covers of a poset).

[L2]

For $0 \leq k \leq n$ , $(\binom{n}{k}) k! (n - k)! = n!$ ( $(\binom{n}{k}) k! (n - k)! = n!$ for $k \leq n$ ; hence $(\binom{n}{k}) k! = n^{\underline{k}}$ , the quotient $n! / (k! (n - k)!)$ is a natural number, and $(\binom{n}{k}) = (\binom{n}{n - k})$ ).

[F2]

Finite sums may be indexed by an arbitrary finite set and reindexed without changing their value (The sum $\sum_{i \in S} a_{i}$ over a finite index set, and its product form).

Proof

technique · direct

1.1

Count pairs $(S, C)$ where $S \in F$ and $C$ is a maximal chain containing $S$ . By [L1], the number is $\sum_{S \in F} ∣ S ∣! (n - ∣ S ∣)!$ .

givenL1F2

1.2

A maximal chain contains at most one member of $F$ , because all members of a chain are comparable. Hence the number of pairs is at most the number $n!$ of maximal chains.

givenF1L1

2.1

Combining steps 1.1 and 1.2 and dividing by the positive number $n!$ gives $\sum_{S \in F} ∣ S ∣! (n - ∣ S ∣)! / n! \leq 1$ .

step 1.1step 1.2algebra

3.1

By [L2], each summand in step 2.1 equals $1 / (\binom{n}{∣ S ∣})$ . Substitution yields the asserted LYM inequality.

step 2.1L2algebra∎

Depends on

Used by

Sperner's theorem and its equality cases: a largest antichain is a complete middle level Corollary

Dependency tree · two levels

33 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

M. Keller and W. T. Trotter, Applied Combinatorics, §6.2 (standard reference, not scraped)