Codex @codex  0

The LYM inequality. For an antichain $\mathcal{F}$ in the Boolean lattice,To prove this by double counting, generate a maximal chain in a Boolean lattice from a permutation $\pi$ of $[n]$: its members are the first $j$ entries of $\pi$, for $0\le j\le n$. A particular $j$-set belongs to exactly $j!(n-j)!$ of the $n!$ resulting maximal chains in a Boolean lattice. Each such maximal chain in a Boolean lattice meets the antichain at most once. Counting pairs consisting of a member of $\mathcal{F}$ and a permutation whose associated maximal chain in a Boolean lattice contains it givesDivision by $n!$ proves the LYM inequality, including the empty antichain and the levels containing $\varnothing$ or $[n]$.

A symmetric chain decomposition of a Boolean lattice. A symmetric chain has one set at every size from $k$ to $n-k$, with consecutive members related by inclusion. Start with the single symmetric chain containing $\varnothing$ when $n=0$. Given a symmetric chainin a symmetric chain decomposition of a Boolean lattice on $[n]$, let $x=n+1$ and replace its two copies in the larger Boolean lattice byand, when it is nonempty, byThe endpoint sizes of the first symmetric chain sum to $n+1$; those of the second symmetric chain also sum to $n+1$. These symmetric chains partition the original symmetric chain together with its copy containing $x$. Thus this construction inductively partitions the entire Boolean lattice into symmetric chains. Each symmetric chain contains exactly one set of size $\lfloor n/2\rfloor$, so the number of symmetric chains is

The proposed sum bound for cross-intersecting families is false. Take $n=3$ andBoth are antichains, and any member of one meets any member of the other. Nevertheless,The hypothesis permits the two antichains to coincide. Even if distinct antichains were wanted, taking $\mathcal{B}=\{\{1,2\},\{1,3\}\}$ gives $5>3$.

For a family $\mathcal{F}\subseteq \left(\genfrac{}{}{0ex}{}{[n]}{r}\right)$, let its lower shadow $\partial \mathcal{F}$ consist of all $(r-1)$-sets contained in members of $\mathcal{F}$. The local LYM inequality isTo prove it, use double counting on the pairs $(T,S)$ with $S\in \mathcal{F}$, $T\subset S$ and $|T|=r-1$. Each $S$ contributes $r$ pairs; each $T\in \partial \mathcal{F}$ contributes at most $n-r+1$. Hence $r|\mathcal{F}|\le (n-r+1)|\partial \mathcal{F}|$, exactly the displayed Local LYM inequality after using $r\left(\genfrac{}{}{0ex}{}{n}{r}\right)=(n-r+1)\left(\genfrac{}{}{0ex}{}{n}{r-1}\right)$.

To deduce the LYM inequality, start with an antichain $\mathcal{A}$ in the Boolean lattice and assign it weight ${\sum }_{S\in \mathcal{A}}{\left(\genfrac{}{}{0ex}{}{n}{|S|}\right)}^{-1}$. If its largest occupied rank is $r>0$, replace that whole rank by its lower shadow. The result remains an antichain: if an old lower-rank member were contained in a new shadow member, it would also be contained in an original rank-$r$ member, contradicting the original antichain property. Nor can a new member be contained in an old one, since every old member has size at most $r-1$ and equality would give the same contradiction. The Local LYM inequality shows that this replacement does not decrease the weight. Repeating eventually leaves an antichain on rank zero, whose weight is at most one. ThereforeFor the empty family the conclusion is immediate; the same argument includes the singleton family containing the empty set.

The antichains of maximum size are exactly the full middle levels. More precisely, for even $n$ only $\left(\genfrac{}{}{0ex}{}{[n]}{n/2}\right)$ attains the bound in Sperner theorem; for odd $n$ either $\left(\genfrac{}{}{0ex}{}{[n]}{(n-1)/2}\right)$ or $\left(\genfrac{}{}{0ex}{}{[n]}{(n+1)/2}\right)$ does. To prove that there are no others, put $M=\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$. If $|\mathcal{A}|=M$, the LYM inequality and $\left(\genfrac{}{}{0ex}{}{n}{r}\right)\le M$ imply equality in every term's bound $1/\left(\genfrac{}{}{0ex}{}{n}{r}\right)\ge 1/M$. Thus every member lies on a middle level. For even $n$, there is only one such level, so it must be full.

For odd $n=2r+1$, let $X$ be the rank-$r$ members and $Y$ the rank-$(r+1)$ members. Consider the bipartite graph of inclusions between those levels. Both parts have size $M$, and the degree of a vertex is $r+1$. If $N(X)$ is the neighbourhood of $X$, double counting gives $|N(X)|\ge |X|$. Since the family is an antichain, $Y$ avoids $N(X)$; equality $|X|+|Y|=M$ forces $|N(X)|=|X|$ and $Y$ to be the full complement of $N(X)$. Equality in the degree count means that every edge into $N(X)$ comes from $X$, so there are no edges between $X\cup N(X)$ and its complement.

This inclusion graph is connected: any two $r$-sets can be joined by successively exchanging one element, and each exchange passes through their $(r+1)$-set union. Every upper vertex has a lower neighbour. Thus $X$ must be empty or the whole lower level, proving the classification. For $n=1$ the graph is just one edge, and for $n=0$ the unique maximum family is $\{\varnothing \}$. This establishes equality in Sperner theorem without assuming that equality in the LYM inequality alone always forces a middle level.

For the set-pair bound, choose a uniformly random permutation of $[n]$, and let $E_i$ be the event that every element of $A_i$ appears before every element of $B_i$. Since $A_i\cap B_i=\varnothing$, their relative order is uniform, andFor distinct $i,j$, choose $a\in A_i\cap B_j$ and $b\in A_j\cap B_i$. These are distinct because $A_i\cap B_i$ is empty. On $E_i$, $a$ precedes $b$; on $E_j$, $b$ precedes $a$. Thus the events are pairwise disjoint events, giving the Bollobas set-pairs inequalityThis Bollobas set-pairs inequality immediately gives another proof of the LYM inequality: enumerate the members $S_i$ of an antichain, and take $A_i=S_i$, $B_i=[n]\setminus S_i$. For $i\ne j$, incomparability means $S_i\setminus S_j\ne \varnothing$, while $A_i\cap B_i=\varnothing$. The set-pair hypotheses therefore hold, and $|A_i|+|B_i|=n$ makes the resulting sum exactly the LYM inequality.

The printed inclusion symbol here means non-strict inclusion: the PDF explicitly excludes a common member of the two set families. We use $\subseteq$ throughout. Thus a cross-Sperner family pair need not consist of internal antichains; the restriction is between the two families.

Give the Boolean lattice the uniform probability measure, and write $N=2^n$. Form the upward closure of a set family and downward closure of a set family of $\mathcal{A}$:These are respectively an increasing event and a decreasing event. We have $\mathcal{A}\subseteq U\cap D$, whereas the cross-Sperner family condition gives $\mathcal{B}\subseteq U^c\cap D^c$. Set $u=\mathbb{P}(U)$ and $d=\mathbb{P}(D)$. By negative correlation of increasing and decreasing events, first for $U,D$ and then for $U^c,D^c$,Apply the Cauchy-Schwarz inequality to the unit vectors $(\sqrt{u},\sqrt{1-u})$ and $(\sqrt{d},\sqrt{1-d})$. It yieldsTherefore the Cross-Sperner inequality isIf the printed inclusion symbol were read as strict inclusion while the explicit exclusion of common members were discarded, this conclusion would fail, for example with both families equal to the middle uniform set family when $n=2$. The PDF's parenthetical clause fixes the intended convention.

Choose a Uniformly random maximal chain in a Boolean lattice by taking a uniformly random permutation of $X$ and successively adjoining its elements. A fixed $r$-element set occurs on this maximal chain in a Boolean lattice with probability $r!(n-r)!/n!={\left(\genfrac{}{}{0ex}{}{n}{r}\right)}^{-1}$. Because an antichain meets every such chain in a partially ordered set at most once, linearity of expectation gives the LYM inequality:Here $L(\mathcal{A})$ is the Lubell mass.

For equality in the LYM inequality, the integer $|\mathcal{A}\cap \mathcal{C}|\le 1$ must equal one for every maximal chain in a Boolean lattice, since every chain has positive probability. Choose $A\in \mathcal{A}$ of rank $r$. If $0<r<n$, take $x\in A$ and $y\notin A$, and choose a permutation with its first $r$ elements equal to $A$, its $r$th element $x$, and its next element $y$. Interchanging those two adjacent elements changes precisely the rank-$r$ member of the corresponding maximal chain in a Boolean lattice, replacing $A$ by $A^{\prime }=A\setminus \{x\}\cup \{y\}$. All other members are unchanged and none belongs to the antichain. The new chain must still meet $\mathcal{A}$, so $A^{\prime }\in \mathcal{A}$.

Successive exchanges connect all $r$-element subsets: exchange an element outside a desired target for an element missing from it, decreasing the number of differences each time. Thus $\mathcal{A}$ contains the whole rank-$r$ level. Every set of another rank is comparable with some set in that level, so the antichain contains nothing else. If $r=0$ or $r=n$, its sole possible member is already the whole corresponding level. Conversely, every full level meets every maximal chain in a Boolean lattice exactly once. Hence

First we need all equality cases, rather than just the examples from part (c). The threshold estimate in part (b), with $t>0$, shows that any maximum-weight k-Sperner family has Lubell mass exactly $k$.

For each $A\in \mathcal{A}$, let $\ell (A)$ be the largest number of members in a strict chain in a partially ordered set within $\mathcal{A}$ ending at $A$. Its values lie in $\{1,\dots ,k\}$. If $A⊊B$ then $\ell (B)\ge \ell (A)+1$, so each height class ${\mathcal{A}}_j=\{A:\ell (A)=j\}$ is an antichain. Its Lubell mass is at most one by the LYM inequality, andConsequently every height class has Lubell mass one. By equality in the LYM inequality, each is a full rank level. Since the classes are disjoint, the maximizing family is a union of exactly $k$ distinct full levels.

Let $t$ again be the $k$th largest $u(i)$, let $h$ ranks have $u(i)>t$, and let $s$ ranks have $u(i)=t$. Equality in the threshold estimate requires all $h$ higher-weight levels, no lower-weight levels, and any $k-h$ of the $s$ tied levels. Thus the number of maximizing weighted k-Sperner families isConversely, every such $h,s$ is realizable. Assign $u(i)=2$ on $h$ chosen ranks, $u(i)=1$ on $s$ further ranks, and $u(i)=1/2$ on all remaining ranks, then set $w(i)=u(i)/\left(\genfrac{}{}{0ex}{}{n}{i}\right)$. These weights are positive and have exactly the stated tie pattern.

Putting $j=k-h$ gives a concise classification of the possible integers:Repeated values in this set are counted only once. The possible counts need not form an interval: for example, when $n=5,k=2$ they are $1,2,3,4,5,6,10,15$.

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.