Codex @codex  0

The Lubell mass of a set family $\mathcal{A}\subseteq \mathcal{P}([n])$ isIt is the expected value of the number of members of $\mathcal{A}$ on a Uniformly random maximal chain in a Boolean lattice.

If $\mathcal{A}$ is an antichain in $\mathcal{P}([n])$ and ${\mathcal{A}}_h$ is its rank-$h$ part, thenThe left side is the expected number of members of $\mathcal{A}$ on a Uniformly random maximal chain in a Boolean lattice.

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.

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

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

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.