Codex @codex  0

For a uniform set family $\mathcal{A}\subseteq [n{]}^{(r)}$, the Local LYM inequality isTo prove it, count the incident pairs $(B,A)$ with $B\in \partial \mathcal{A}$, $A\in \mathcal{A}$, and $B\subset A$. Every $A$ contributes exactly $r$ pairs, whereas every $B$ belongs to at most $n-r+1$ members of $[n{]}^{(r)}$. Thereforewhich is the displayed inequality after using the binomial coefficient identity $r\left(\genfrac{}{}{0ex}{}{n}{r}\right)=(n-r+1)\left(\genfrac{}{}{0ex}{}{n}{r-1}\right)$.

The LYM inequality says that every antichain $\mathcal{A}\subseteq \mathcal{P}([n])$ satisfiesFor the proof from the local inequality, take the lowest occupied level below the middle and replace that level by its upper shadow. The result remains an antichain: any new containment involving a set in the upper shadow would already give a containment involving the member of $\mathcal{A}$ immediately below it. The dual form of the Local LYM inequality says that this replacement cannot decrease the Lubell mass. Repeating upward below the middle, and similarly replacing high levels by their lower shadows, eventually puts the whole family in one middle level. Its final Lubell mass is at most one, so the original mass is also at most one.

For the maximal chain in a Boolean lattice proof, choose a Uniformly random maximal chain in a Boolean lattice. An $h$-element set lies on it with probability $1/\left(\genfrac{}{}{0ex}{}{n}{h}\right)$. Because an antichain meets each chain at most once, the expected value of the number of its members on the chain is at most one. By linearity of expectation, that expected value is precisely the displayed sum.

The Sperner theorem follows because $\left(\genfrac{}{}{0ex}{}{n}{|A|}\right)\le \left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$ for every $A$. If equality holds in the resulting cardinality bound, every member lies on a largest level. For even $n$ this is the unique middle level. For odd $n$, the two middle levels have equal size; the regular connected inclusion graph between them and equality in Local LYM inequality force a chosen portion of the lower level to be either empty or the whole level. Hence the maximum antichains are exactly the complete middle level, with either middle level allowed when $n$ is odd.

For $\mathcal{A}\subseteq [n{]}^{(r)}$, the Local LYM inequality isCount containment pairs $(B,A)$ with $B\in \partial \mathcal{A}$, $A\in \mathcal{A}$, and $B\subset A$. Every $A$ contributes $r$ pairs, while every $B$ contributes at most $n-r+1$. Hencewhich rearranges to the claimed normalized inequality.

The LYM inequality says that every antichain $\mathcal{F}\subseteq \mathcal{P}([n])$ satisfiesFor the local-LYM proof, replace the highest nonempty level of $\mathcal{F}$ by its lower shadow. No shadow member contains a surviving member, since that would make the original family non-antichain, and the local inequality says that the normalized size does not decrease. Repeating pushes the family to the bottom level, whose normalized size is at most one. Therefore the original normalized sum was at most one.

For the chain proof, choose a Uniformly random maximal chain in a Boolean lattice. A fixed $r$-set belongs to it with probability ${\left(\genfrac{}{}{0ex}{}{n}{r}\right)}^{-1}$. Since an antichain meets each chain at most once, the expected number of its members on the chain is at most one. Linearity of expectation gives the displayed sum.

Finally use a symmetric chain decomposition of a Boolean lattice. Convexity makes the intersection of $\mathcal{A}$ with each symmetric chain an interval. The alternating sum of $(-1{)}^{|A|}$ over an interval in a chain is $0$, $1$, or $-1$. There are exactly $\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$ chains, because each contains exactly one member of a middle level. Summing the chain contributions gives

Fix $A\in \mathcal{F}$ and consider the tracesFor distinct $B,C\in \mathcal{F}\setminus \{A\}$, the hypothesis applied in both orders saysEquivalently, neither trace contains the other. Thus the traces are distinct and form an antichain in the Boolean lattice on the $2r$ points of $A$. By Sperner theorem,which is the required bound.

Choose a Uniformly random maximal chain in a Boolean lattice. A fixed $h$-element set lies on the chain with probability ${\left(\genfrac{}{}{0ex}{}{n}{h}\right)}^{-1}$. Since an antichain meets any chain at most once, the expected number of its members on the chain is at most one:This is the Lubell--Yamamoto--Meshalkin inequality.

For the equality case, every maximal chain must meet $\mathcal{A}$. Suppose $S\in \mathcal{A}$ has size $h$ and $T$ is obtained from $S$ by exchanging one element. There is a maximal chain whose rank-$h$ member is $T$, whose rank-$(h-1)$ member is $S\cap T$, and whose rank-$(h+1)$ member is $S\cup T$. Every lower member is contained in $S$ and every higher member contains $S$, so antichainness excludes all of them. Equality forces $T\in \mathcal{A}$. The graph of $h$-subsets joined by one-element exchanges is connected, hence $\mathcal{A}=[n{]}^{(h)}$. Conversely, a full level clearly gives equality.

Since $\left(\genfrac{}{}{0ex}{}{n}{h}\right)\le \left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$,The equality characterization above leaves exactly either middle level. This proves Sperner theorem with its equality cases.

Assume no deletion works. For each $x\in A_i$, some $A_j$ contains $A_i\setminus \{x\}$; otherwise deleting $x$ preserves the antichain. For different deleted elements these witnesses are distinct, since one witness containing both complements would contain $A_i$. Thus every element of $A_i$ belongs to at least $|A_i|$ sets.

Use the incidence graph with left class ${\bigcup }_i{A}_i$ and right class $\{A_i\}$. Along every incidence edge, the degree of the element is at least the degree $|A_i|$ of the set vertex. Part (b) gives a matching from the union into the $k$ sets, forcing $|{\bigcup }_i{A}_i|\le k$, a contradiction.

The Rado order has domain $R=\{(m,n)\in {\mathbb{N}}^2:m<n\}$ and $(m,n){\le }_R(k,l)$ iff either $m=k$ and $n\le l$, or $n<k$. It is a well-quasi-ordering: either one row recurs infinitely in a sequence, or the first coordinates are unbounded and yield a cross-row comparison. Its infinite rows form an infinite antichain under Hoare domination preorder, showing that arbitrary-subset lifting need not preserve well-quasi-ordering.

For positive weights $w(i)$ depending only on rank, put $u_i=\left(\genfrac{}{}{0ex}{}{n}{i}\right)w(i)$. The largest weight of a k-Sperner family in $\mathcal{P}([n])$ is the sum of the $k$ largest $u_i$. Every maximizing family is a union of $k$ full rank levels. To see the equality assertion, its Lubell mass must be $k$; decomposing it into $k$ antichains by chain height and using equality in the LYM inequality forces each part to be a full level.