Codex @codex  0

An antichain in the Boolean lattice has Lubell mass one if and only if it is a full rank level. Equality means every maximal chain in a Boolean lattice meets the family exactly once. Swapping two adjacent entries in the defining permutation then forces the family to contain every set obtained from one member by exchanging an included and an excluded element, hence every set of that rank.

A $k$-Sperner family contains no inclusion chain of length $k+1$. Every maximal chain in a Boolean lattice therefore meets it in at most $k$ members, so its Lubell mass is at most $k$.

Choose a uniformly random permutation of $[n]$ and take its initial segments. This produces a Uniformly random maximal chain in a Boolean lattice. A fixed $r$-set belongs to this chain with probability $r!(n-r)!/n!={\left(\genfrac{}{}{0ex}{}{n}{r}\right)}^{-1}$. An antichain meets the chain at most once, so taking the expected value of the number of meetings proves the LYM inequality:In particular the Sperner theorem bound follows by multiplying each summand by at most the largest binomial coefficient.

For the vector request, an ordering by ordinary subset need not work: distinct vectors may cancel. Instead, write $s_A={\sum }_{i\in A}{x}_i$ and construct a separated block decomposition for vector subset sums. A block is separated if distinct labeled members have subset sums at distance at least one. We prove that the labeled subsets of $[n]$ can be partitioned into separated blocks, withblocks of size $n-2r+1$, for $0\le r\le \lfloor n/2\rfloor$, with $\left(\genfrac{}{}{0ex}{}{n}{-1}\right)=0$.

For $n=0$ the one subset forms one block. Suppose a block of sums $z_1,\dots ,z_{\ell }$ has already been constructed for $n-1$ vectors, and let $x=x_n$. Choose $z_{\ast }$ minimizing $z_j\cdot x$ in the block. Replace the two copies of the block, with and without the new coordinate, by the following two blocks:The old labels are retained, so these partition the two copies even if equal sums occur in different blocks. Translation preserves separation in the first translated portion, and the second block is a subset of the old separated block. For the new cross pairs, Cauchy-Schwarz inequality givesThus both new blocks are separated. Their sizes are $\ell +1$ and $\ell -1$, omitting an empty block. The resulting size-profile recurrence is $b_{n,r}=b_{n-1,r}+b_{n-1,r-1}$, and Pascal's identity verifies the displayed binomial-difference formula, including the even middle boundary. The total number of blocks telescopes to $\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$.

A signed sum associated with $A=\{i:{ϵ}_i=1\}$ is $2s_A-{\sum }_i{x}_i$. If two signed sums lie in the open ball of radius one, their difference has norm less than two, so their subset sums have distance less than one. At most one can therefore lie in any separated block. Hence the Littlewood-Offord inequality isThe counting is by sign choices, not by distinct numerical values of the sums. The open-ball condition handles the equality-distance boundary correctly.

For the last request take real coefficients. Absorb their signs into the choices ${ϵ}_i$, so all coefficients are positive and at least one. A signed-sum real interval of length four corresponds to a subset-sum real interval of length two. A strict three-member inclusion chain $A⊊B⊊C$ would have $s_C-s_A\ge 2$, which cannot occur in that open real interval. Thus its set family is a k-Sperner family with $k=2$. Every maximal chain in a Boolean lattice meets it at most twice, yielding ${\sum }_r|{\mathcal{F}}_r|/(\genfrac{}{}{0ex}{}{n}{r})\le 2$. Write $f_r=|{\mathcal{F}}_r|/(\genfrac{}{}{0ex}{}{n}{r})$, so $0\le f_r\le 1$ and ${\sum }_r{f}_r\le 2$. If $B_1\ge B_2$ are the two largest binomial coefficients and $f_{\ast }$ is the fraction at a largest level, then $|\mathcal{F}|\le B_1{f}_{\ast }+B_2(2-f_{\ast })\le B_1+B_2$. This proves the two-level Littlewood-Offord bound:It is the greatest possible number uniformly over choices of coefficients and center. For even $n=2m$, take every coefficient equal to one and center $a=-1$: the real interval $(-3,1)$ contains the sum levels $-2,0$, of multiplicities $\left(\genfrac{}{}{0ex}{}{n}{m-1}\right),\left(\genfrac{}{}{0ex}{}{n}{m}\right)$. For odd $n=2m+1$, take center zero, giving levels $-1,1$, each of multiplicity $\left(\genfrac{}{}{0ex}{}{n}{m}\right)$. These attain the bound. For $n=0$ the only sign choice gives the separate maximum one. Attainment here is at the exhibited centers; it need not hold at every prescribed center.

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.

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$.

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

A k-Sperner family meets every maximal chain in a Boolean lattice in at most $k$ members. The random-chain calculation in part (a) therefore gives the generalized LYM inequality $L(\mathcal{A})\le k$. Define the proportion of rank $i$ that is present byThen ${\sum }_i{x}_i=L(\mathcal{A})\le k$ and $w(\mathcal{A})={\sum }_{i}u(i)x_i$. This reduces the weighted theorem for k-Sperner families to allocating at most $k$ units of mass among ranks, each of capacity one.

To handle ties explicitly, let $t>0$ be the $k$th largest value among the $u(i)$, let $H=\{i:u(i)>t\}$, and put $h=|H|<k$. ThenThe last expression is exactly the sum of the $k$ largest rank weights, with multiplicity. Writing those values in descending order as $u_{(1)},\dots ,u_{(n+1)}$, the answer is

The hypothesis says exactly that $\mathcal{A}$ is a k-Sperner family with $k=2$: it contains no three members forming a strict inclusion chain. Every maximal chain in a Boolean lattice consequently contains at most two members of $\mathcal{A}$, so the same random-chain argument gives $\lambda (\mathcal{A})\le 2$. For a fixed amount of Lubell mass, cardinality is maximized by using the levels with the two largest binomial coefficients. The Erdős theorem on k-Sperner families therefore givesThe bound is attained by taking the union of two levels having those sizes.

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.