Codex @codex  0

The bipartite inclusion graph between consecutive nonempty ranks of the Boolean lattice is connected. Two rank-$r$ sets differing by one exchanged element share their rank-$(r+1)$ union as a neighbour; successive exchanges connect any two rank-$r$ sets. Every upper vertex has a lower neighbour. For the two middle ranks of an odd-dimensional Boolean lattice the graph is regular, so equality in the Local LYM inequality for a nonempty upper family forces the whole upper rank: equality admits no edges from its lower shadow to the remaining upper vertices.

Repeatedly applying the Local LYM inequality to upper shadows givesfor $\mathcal{A}\subseteq [n{]}^{(r)}$ and $0\le s\le n-r$. The analogous statement for iterated lower shadows follows directly from the stated lower-shadow form.

For $1\le r\le n$ and a rank-$r$ uniform set family $\mathcal{F}$, let $\partial \mathcal{F}$ be its lower shadow. Count pairs $(B,A)$ with $A\in \mathcal{F}$, $B\subset A$ and $|B|=r-1$. Every $A$ contributes $r$ pairs, whereas each shadow member lies in at most $n-r+1$ rank-$r$ sets. ThusThis is the Local LYM inequality. Complementation gives the upper-shadow form $|\nabla \mathcal{F}|/\left(\genfrac{}{}{0ex}{}{n}{r+1}\right)\ge |\mathcal{F}|/(\genfrac{}{}{0ex}{}{n}{r})$ for $r<n$.

To deduce the LYM inequality, let $\mathcal{A}$ be an antichain, ${\mathcal{A}}_r$ its rank-$r$ part, and $U_r$ all rank-$r$ sets containing some member of $\mathcal{A}$. For $r\ge 1$,The union is disjoint because an antichain member cannot contain a smaller member; every other set of $U_r$ contains a rank-$(r-1)$ superset of its smaller witnessing member. Apply the upper local inequality and put $u_r=|U_r|/(\genfrac{}{}{0ex}{}{n}{r})$:Since $u_0=|{\mathcal{A}}_0|$ and $u_n\le 1$, summing givesThus the deduction uses the local inequality explicitly, rather than quoting a separate maximal-chain argument.

Let $M=\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$, the largest rank size. The LYM sum is at least $|\mathcal{A}|/M$, proving the Sperner theorem bound. If $|\mathcal{A}|=M$, equality forces all its members onto ranks with binomial coefficient $M$. For even $n$, there is only the middle rank, so the family is that whole rank.

For $n=2m+1$, only ranks $m,m+1$ are possible, each of size $M$. Let $\mathcal{B}={\mathcal{A}}_{m+1}$. Antichainness gives ${\mathcal{A}}_m\cap \partial \mathcal{B}=\varnothing$, and local LYM gives $|\partial \mathcal{B}|\ge |\mathcal{B}|$. Since the two antichain parts together have size $M$, equality must hold. The inclusion graph between these ranks is $(m+1)$-regular on each side. Its edges from $\mathcal{B}$ already number $(m+1)|\mathcal{B}|$, so equality leaves no edge from $\partial \mathcal{B}$ to the complementary upper vertices.

The graph is connected: exchanging one element between two $m$-sets joins them through their $(m+1)$-element union, and successive exchanges connect all lower vertices; every upper vertex has a lower neighbour. Consequently $\mathcal{B}$ is either empty or the entire upper rank. This connectedness of adjacent-level incidence in a Boolean lattice excludes mixed extremizers. HenceThere is one choice for even $n$ and two for odd $n$. For $n=0$, the sole maximum family is $\{\varnothing \}$, agreeing with this description.

Write $\left(\genfrac{}{}{0ex}{}{[n]}{k}\right)$ for the $k$th uniform layer of the Boolean cube. For $\mathcal{F}\subseteq \left(\genfrac{}{}{0ex}{}{[n]}{k}\right)$, $1\le k\le n$, its lower shadow is $\partial \mathcal{F}=\{B:|B|=k-1,B\subset A\text{ for some }A\in \mathcal{F}\}$. The Local LYM inequality statesTo prove it, count pairs $(B,A)$ with $A\in \mathcal{F}$, $B\subset A$ and $|B|=k-1$. Each $A$ contributes $k$ pairs; each member of the lower shadow contributes at most $n-k+1$. Thus $k|\mathcal{F}|\le (n-k+1)|\partial \mathcal{F}|$, which is exactly the displayed Local LYM inequality. The corresponding upper shadow inequality follows either by taking complements or by counting upward inclusion pairs.

For an antichain $\mathcal{A}\subseteq \mathcal{P}([n])$, put ${\mathcal{A}}_k=\mathcal{A}\cap \left(\genfrac{}{}{0ex}{}{[n]}{k}\right)$. The LYM inequality isFor the first proof, set ${\mathcal{B}}_n={\mathcal{A}}_n$ and recursively ${\mathcal{B}}_k={\mathcal{A}}_k\cup \partial {\mathcal{B}}_{k+1}$. Every member of ${\mathcal{B}}_{k+1}$ is a subset of an original member of $\mathcal{A}$ of size at least $k+1$. Consequently ${\mathcal{A}}_k$ and $\partial {\mathcal{B}}_{k+1}$ are disjoint: otherwise one original member would properly contain another, contradicting the antichain condition. The Local LYM inequality now givesIterating down to $k=0$ bounds the desired sum by $|{\mathcal{B}}_0|\le 1$, proving the LYM inequality.

For the second proof, a permutation $(i_1,\dots ,i_n)$ determines a maximal chain in a Boolean lattice through the successive initial subsets $\varnothing ,\{i_1\},\dots ,[n]$. A member $A$ of size $k$ lies on exactly $k!(n-k)!$ of these $n!$ maximal chains in a Boolean lattice. An antichain meets each such chain in a partially ordered set at most once. Counting its incidences with the maximal chains in a Boolean lattice therefore yields ${\sum }_{A\in \mathcal{A}}|A|!(n-|A|)!\le n!$. Division by $n!$ is the LYM inequality again.

The Sperner theorem says that an antichain has at most $M=\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$ members. Indeed $\left(\genfrac{}{}{0ex}{}{n}{k}\right)\le M$ for every $k$, soThe middle uniform layer of the Boolean cube attains the bound. For equality in Sperner theorem, equality throughout forces every member to lie in a layer of maximum size. If $n=2k$, this forces $\mathcal{A}=\left(\genfrac{}{}{0ex}{}{[n]}{k}\right)$.

If $n=2k+1$, only ranks $k$ and $k+1$ are possible. Let $\mathcal{L}={\mathcal{A}}_k$, $\mathcal{U}={\mathcal{A}}_{k+1}$, and $\mathcal{S}=\nabla \mathcal{L}$ be the upper shadow. The antichain condition gives $\mathcal{U}\cap \mathcal{S}=\varnothing$. The Local LYM inequality for the two equally sized middle layers gives $|\mathcal{S}|\ge |\mathcal{L}|$, while $|\mathcal{L}|+|\mathcal{U}|=M$ forces $|\mathcal{S}|=|\mathcal{L}|$ and $\mathcal{U}=\left(\genfrac{}{}{0ex}{}{[n]}{k+1}\right)\setminus \mathcal{S}$.

Consider the inclusion bipartite graph between these two middle layers. It is a $(k+1)$-regular graph. Since $|\mathcal{S}|=|\mathcal{L}|$, all $(k+1)|\mathcal{S}|$ edges incident to $\mathcal{S}$ must come from $\mathcal{L}$; there are no edges from its complement on the lower side into $\mathcal{S}$. This bipartite graph is a connected graph: any two $k$-subsets can be joined by single-element exchanges, and each exchange passes through their common $(k+1)$-superset; every upper vertex has a lower neighbour. For $k=0$ it is just one edge. Hence either $\mathcal{L}=\varnothing$ or $\mathcal{L}$ is the whole lower layer. We have proved the complete classification:The two possibilities coincide for even $n$; for $n=0$ the unique maximum antichain is $\{\varnothing \}$.

Finally enumerate the members of the separating set system as $A_1,\dots ,A_m$ and encode each point $i\in [n]$ by $T_i=\{a\in [m]:i\in A_a\}$. Separation of the ordered pair $(i,j)$ means $T_i\setminus T_j\ne \varnothing$. Applying the hypothesis also to $(j,i)$ shows that the $n$ sets $T_i$ are distinct and pairwise incomparable. They form an antichain in $\mathcal{P}([m])$, so the Sperner theorem immediately gives

Write $[n{]}^{(r)}$ for the rank-$r$ uniform layer of the Boolean cube. For a uniform set family $\mathcal{F}\subseteq [n{]}^{(r)}$, with $1\le r\le n$, let $\partial \mathcal{F}$ be its lower shadow. The Local LYM inequality isFor its proof, count incidences $(B,A)$ with $A\in \mathcal{F}$, $B\subset A$, and $|B|=r-1$. Each member of $\mathcal{F}$ contributes $r$ incidences, while each member of the lower shadow contributes at most $n-r+1$. Thus $r|\mathcal{F}|\le (n-r+1)|\partial \mathcal{F}|$, which is the displayed bound by the ratio of consecutive binomial coefficients. Complementing every set gives the corresponding upper shadow bound, $|\nabla \mathcal{F}|/\left(\genfrac{}{}{0ex}{}{n}{r+1}\right)\ge |\mathcal{F}|/(\genfrac{}{}{0ex}{}{n}{r})$ for $r<n$.

For an antichain $\mathcal{A}$ in the Boolean lattice, the LYM inequality isHere is the proof using the Local LYM inequality. Denote the rank-$r$ part by ${\mathcal{A}}_r$, and let ${\mathcal{D}}_r$ consist of the $r$-sets containing some member of $\mathcal{A}$ of size at most $r$. These families satisfyThe union is disjoint because a member of the antichain cannot contain a strictly smaller member. Apply the upper shadow form of the Local LYM inequality to ${\mathcal{D}}_{r-1}$:Iterating gives a bound for the entire sum by $|{\mathcal{D}}_n|/(\genfrac{}{}{0ex}{}{n}{n})\le 1$. This also covers the empty antichain and an antichain containing the empty set.

For the second proof, each permutation of $[n]$ specifies a maximal chain in a Boolean lattice by taking its successive prefixes. There are $n!$ such maximal chains in a Boolean lattice, and a fixed $r$-set belongs to $r!(n-r)!$ of them. A maximal chain in a Boolean lattice meets an antichain at most once. Double counting these incidences therefore gives ${\sum }_r|{\mathcal{A}}_r|r!(n-r)!\le n!$, exactly the LYM inequality.

The Sperner theorem says that an antichain in $\mathcal{P}([n])$ has at most $\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$ members; a full middle rank attains this bound. Indeed, every binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$ is at most the central one, so the LYM inequality givesNow let $\mathcal{F}$ be an intersection-free uniform set family. If it is empty, there is nothing to prove. Fix $X\in \mathcal{F}$ and consider the tracesIf $A,B\ne X$ are distinct and $X\cap A\subseteq X\cap B$, then $X\cap A\subseteq B$. This contradicts the defining restriction on the three distinct members $X,A,B$. The intersection has size less than $r$, so it is a proper subset of $B$ even if the printed subset symbol is interpreted strictly. In particular, equal traces are impossible, and the traces form an antichain. Thus $|\mathcal{T}|=|\mathcal{F}|-1$. Applying the Sperner theorem to the $r$-element ground set $X$ proves the antichain trace bound for intersection-free familiesThe argument also handles $r=0$: a uniform set family then has at most one member.

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.

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