Codex @codex  0

Proceed by induction on the ground-set size, starting with the one-element chain $\{\varnothing \}$ in the Boolean lattice on no coordinates. Suppose a symmetric chain decomposition of a Boolean lattice on $[n]$ has been constructed. Write one of its chains asOn adjoining the new coordinate $v=n+1$, replace its two copies byand, when nonempty,The first chain has endpoint ranks $r,n-r+1$, summing to $n+1$. The second has endpoint ranks $r+1,n-r$, also summing to $n+1$. Both are saturated chains, increasing rank by one at every step. If the original chain was a singleton, the second chain is omitted.

These new chains are disjoint: the first contains every old set without $v$ and just the last old set with $v$; the second contains precisely the remaining old sets with $v$. Thus together they cover both lifted copies of the old chain. Different old chains have disjoint copies, so performing this construction for each yields a partition of all subsets of $[n+1]$ into symmetric chains. This completes the induction and proves a symmetric chain partition exists for every $n$.

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

The Hall marriage theorem states that a finite bipartite graph with vertex classes $U$ and $V$ has a matching in a graph saturating $U$ if and only ifNecessity is immediate: distinct vertices of $A$ must be matched to distinct vertices of $N(A)$.

For sufficiency, induct on $|U|$. If every nonempty proper $A\subset U$ satisfies the strict bound $|N(A)|\ge |A|+1$, choose any edge $uv$ and delete its endpoints. Every $A\subseteq U\setminus \{u\}$ loses at most the neighbour $v$, so Hall's condition remains true; induction supplies a matching of the smaller graph, to which $uv$ is added.

Otherwise there is a nonempty proper tight set $A\subset U$ with $|N(A)|=|A|$. Hall's condition holds on the induced graph with parts $A,N(A)$, so induction matches $A$. For $B\subseteq U\setminus A$, Hall's condition on $A\cup B$ givesand hence $|N(B)\setminus N(A)|\ge |B|$. Induction therefore matches $U\setminus A$ into $V\setminus N(A)$. The two matchings are disjoint and together saturate $U$, completing the proof through Hall induction through a tight set.

Identify a subset of $[n]$ with its binary characteristic vector. Then $Q$ is the hypercube graph, and every edge changes set size by exactly one. The induced subgraph on $X_{i-1}\cup X_i$ is therefore bipartite with those two levels as its vertex classes.

Let $\mathcal{A}\subseteq X_{i-1}$. Every member of $\mathcal{A}$ has $n-i+1$ neighbours in $X_i$, obtained by adding one element, while every member of $N(\mathcal{A})$ is incident with at most $i$ of these edges. Double-counting the edges between the two families givesSince $i\le n/2$, we have $n-i+1\ge i$, and hence $|N(\mathcal{A})|\ge |\mathcal{A}|$. Hall's theorem yields the requested adjacent-level matching in a Boolean lattice, saturating $X_{i-1}$.

Finally, every chain in a partially ordered set in the Boolean lattice contains at most one member of the middle level $X_{n/2}$. Any chain partition therefore uses at leastchains.

For every $i\le n/2$, choose one of the matchings just constructed and orient its edges upward. These edges partition all levels at or below $n/2$ into chains ending at distinct middle-level sets. Taking complements gives, for every $i\ge n/2$, a matching from $X_{i+1}$ into $X_i$; orienting its edges upward extends those chains through all upper levels. Every subset belongs to exactly one resulting chain and every chain meets $X_{n/2}$ exactly once. Thus this symmetric chain decomposition of a Boolean lattice has one chain per middle-level set, and the minimum is

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

Proceed by mathematical induction on $n$. The cases $n=0,1$ are immediate. Given a symmetric chain decomposition of a Boolean lattice $\mathcal{P}([n-1])$, consider one of its chainsIt produces the two chainsand, when nonempty,The first runs from rank $r$ to rank $n-r$, and the second from rank $r+1$ to rank $n-1-r$; both endpoint ranks sum to $n$. They are disjoint and together contain the old chain both without and with $n$. Doing this for every old chain partitions $\mathcal{P}([n])$ into symmetric chains.

For Euclidean vectors $x_i$ of length at least one, their labeled subset sums can be partitioned into pairwise distance-at-least-one blocks, with $\left(\genfrac{}{}{0ex}{}{n}{r}\right)-\left(\genfrac{}{}{0ex}{}{n}{r-1}\right)$ blocks of size $n-2r+1$. To extend a separated block by a vector $x$, choose its member $y$ minimizing inner product with $x$. The translated block together with $y$ remains separated, since $(z+x-y)\cdot x\ge \Vert x{\Vert }^2$. The untransformed block with $y$ removed remains separated too. Block sizes change from $\ell$ to $\ell +1,\ell -1$, the same recurrence as a symmetric chain decomposition of a Boolean lattice. There are exactly $\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$ nonempty blocks.

A symmetric chain contains one subset of each size from $k$ to $n-k$, nested by inclusion. Its endpoint ranks sum to $n$. A symmetric chain decomposition of a Boolean lattice partitions all subsets into such chains.