Chains, Antichains, Sperner and Dilworth

For each $x\in P$, let $r(x)$ be the greatest cardinality of a chain whose largest element is $x$. Such a chain exists, since $\{x\}$ is one, and the greatest cardinality exists because the possible values form a nonempty finite subset of $\{1,\dots ,\mathrm{\mid }P\mathrm{\mid }\}$.

Let $C$ be a chain of cardinality $h$, which exists by [F2]. Every antichain contains at most one element of $C$, so any antichain cover of $P$ needs at least $h$ members to cover the $h$ elements of $C$.

If $x<y$, then appending $y$ to a chain of cardinality $r(x)$ ending at $x$ gives a chain ending at $y$, so $r(y)\ge r(x)+1$.

For $i\in \{1,\dots ,h\}$ put $A_i:=\{x\in P:r(x)=i\}$. Each $A_i$ is an antichain, since comparable distinct elements have different $r$-values by step 2.1.

Every $x\in P$ belongs to exactly one $A_i$, and $1\le r(x)\le h$ by the definition of height, so $A_1,\dots ,A_h$ cover $P$.

Step 4.1 gives an antichain cover with $h$ members and step 1.2 rules out every smaller one. Hence the minimum antichain-cover number is $h(P)$.

If $x\in P\setminus A$ were incomparable with every $a\in A$, then $A\cup \{x\}$ would be a larger antichain. Maximality therefore gives an $a\in A$ comparable with $x$.

Let $x\in P^{-}\cap P^{+}$. There are $a,b\in A$ with $b\le x\le a$, hence $b\le a$ by transitivity. Since $A$ is an antichain, $a=b$, and antisymmetry applied to $a\le x\le a$ gives $x=a\in A$.

For the comparable pair from step 1.1, either $x\le a$ and $x\in P^{-}$, or $a\le x$ and $x\in P^{+}$. Every member of $A$ lies in both sets by reflexivity, so $P=P^{-}\cup P^{+}$.

Conversely, every $a\in A$ satisfies $a\le a$, so $A\subseteq P^{-}\cap P^{+}$. Together with step 1.2 this gives $P^{-}\cap P^{+}=A$.

Steps 2.1 and 2.2 establish the asserted union and intersection; restricting the order of $P$ to either subset again gives a partial order.

The antichain $A$ has cardinality $w$ and lies in both $P^{-}$ and $P^{+}$. Since every antichain of either induced subposet is also an antichain of $P$, both $P^{-}$ and $P^{+}$ have width exactly $w$.

Both induced subposets are nonempty because they contain $A$. They are proper subsets of $P$: indeed, $P^{-}=P$ would force $A$ to be exactly the set of maximal elements, since every maximal element of $P$ must then lie in $A$ and no $a\in A$ can have an element strictly above it. Dually, $P^{+}=P$ would force $A$ to be exactly the set of minimal elements. By finiteness, each therefore has cardinality strictly smaller than $\mathrm{\mid }P\mathrm{\mid }$.

By the hypothesis and step 1.1, choose chain covers $\{C_a^{-}:a\in A\}$ of $P^{-}$ and $\{C_a^{+}:a\in A\}$ of $P^{+}$, indexed so that $a\in C_a^{-}\cap C_a^{+}$. Such indexing is possible because each cover has $w=\mathrm{\mid }A\mathrm{\mid }$ chains, each chain contains at most one member of $A$, and all members of $A$ must be covered.

Fix $a\in A$. If $x\in C_a^{-}\subseteq P^{-}$ and $a<x$, then $x\le b$ for some $b\in A$, so $a<b$, contradicting that $A$ is an antichain. Hence every $x\in C_a^{-}$ satisfies $x\le a$. Dually, every $y\in C_a^{+}$ satisfies $a\le y$. Thus $x\le a\le y$ by transitivity, so $C_a^{-}\cup C_a^{+}$ is a chain.

The $w$ chains $C_a^{-}\cup C_a^{+}$ cover $P^{-}\cup P^{+}=P$. Thus they form the required width-sized chain cover of $P$.

For $n\ge 1$, let $Q(n)$ assert that every nonempty poset of cardinality at most $n$ has a chain cover with as many members as its width. The assertion $Q(1)$ holds because a nonempty poset of cardinality at most $1$ is a one-element chain of width $1$.

Assume $Q(n)$, and let $P$ be a poset of cardinality $n+1$ and width $w$. Proving the required cover for this $P$ will prove $Q(n+1)$, since posets of cardinality at most $n$ are already covered by the induction hypothesis.

Every chain contains at most one member of an antichain of cardinality $w$, so every chain cover of $P$ has at least $w$ members.

If there exists a maximum antichain $A$ that is neither the set of all minimal elements nor the set of all maximal elements, choose such an $A$. By [L1], the induced subposets $P^{-}$ and $P^{+}$ are nonempty, have width $w$, and have cardinality at most $n$. The induction hypothesis gives each a chain cover of size its width, and [L1] splices these into a chain cover of $P$ with $w$ chains.

Suppose instead that every maximum antichain is the set of all minimal elements or the set of all maximal elements. Extend any element downward and upward, which terminates because $P$ is finite, to obtain a maximal chain $C$ containing a minimal and a maximal element.

Put $Q:=P\setminus C$. If $Q$ is empty, then $P=C$ is one chain and $w=1$. If $Q$ is nonempty, then $w(Q)\le w-1$: otherwise $Q$ would contain an antichain $B$ of cardinality $w$, making $B$ a maximum antichain of $P$ disjoint from $C$; but every such antichain is, by the present case, all minimal elements or all maximal elements, and $C$ contains an element of each kind.

When $Q$ is nonempty it has cardinality at most $n$, so the induction hypothesis covers it by $w(Q)\le w-1$ chains. Adding the chain $C$ gives a cover of $P$ by at most $w$ chains; it cannot use fewer, because a maximum antichain of cardinality $w$ meets each covering chain in at most one element.

Steps 2.1 and 4.1 prove $Q(n+1)$ in the two exhaustive cases. Thus [L3] proves $Q(n)$ for every $n\ge 1$, and hence gives a width-sized chain cover for the original finite poset. Step 1.3 proves minimality, so the minimum chain-cover number equals the width.

If $r=1$ or $s=1$, any one-term sublist has the required kind, so assume $r,s\ge 2$.

On the index set $\{0,\dots ,N-1\}$ define $i⪯j$ when $i\le j$ and $a_i\le a_j$. The relation is reflexive and transitive componentwise, while $i⪯j⪯i$ forces $i=j$, so it is a partial order. Its chains, read in increasing index order, give strictly increasing sublists because the values are pairwise distinct.

Suppose there is no strictly increasing sublist of length $r$. Then the index-value poset has height at most $r-1$, so [L1] covers its indices by at most $r-1$ antichains. After ordering the covering antichains and removing from each one the indices already assigned to an earlier one, they form a partition into at most $r-1$ antichains.

In an antichain of the index-value poset, increasing the indices strictly decreases the corresponding values: if $i<j$ then $a_i<a_j$ would make $i\prec j$, while equality is excluded. Hence, if there is no strictly decreasing sublist of length $s$, every such antichain has at most $s-1$ members.

Under the simultaneous absence of both required sublists, map each index to the part containing it in the partition from step 2.1. There are at most $r-1$ parts, and step 2.2 says that every fibre has at most $s-1$ elements. Thus [L2] gives $N\le (r-1)(s-1)$, contradicting $N=(r-1)(s-1)+1$.

Therefore at least one of the two sublists exists: a strictly increasing one of length $r$, or a strictly decreasing one of length $s$.

Every ordering $(a_1,\dots ,a_n)$ of $A$ determines the maximal chain $\mathrm{\varnothing }\subset \{a_1\}\subset \{a_1,a_2\}\subset \cdots \subset A$.

Conversely, a maximal chain contains exactly one set of each rank from $0$ to $n$, and the unique element added between consecutive ranks recovers an ordering of $A$. Thus the correspondence in step 1.1 is bijective.

A chain from an ordering contains $S$ exactly when its first $k$ entries are the elements of $S$. There are $k!$ orders for those entries and $(n-k)!$ orders for the remaining entries, independently.

By [L1], there are $n!$ orderings of $A$, so steps 1.1 and 2.1 give exactly $n!$ maximal chains.

The product rule therefore gives exactly $k!(n-k)!$ maximal chains through $S$. Summing this count over the $\left(\genfrac{}{}{0px}{}{n}{k}\right)$ possible $S$ agrees with the total $n!$ by [L3].

Count pairs $(S,C)$ where $S\in \mathcal{F}$ and $C$ is a maximal chain containing $S$. By [L1], the number is ${\sum }_{S\in \mathcal{F}}\mathrm{\mid }S\mathrm{\mid }!(n-\mathrm{\mid }S\mathrm{\mid })!$.

A maximal chain contains at most one member of $\mathcal{F}$, because all members of a chain are comparable. Hence the number of pairs is at most the number $n!$ of maximal chains.

Combining steps 1.1 and 1.2 and dividing by the positive number $n!$ gives ${\sum }_{S\in \mathcal{F}}\mathrm{\mid }S\mathrm{\mid }!(n-\mathrm{\mid }S\mathrm{\mid })!\mathrm{/}n!\le 1$.

By [L2], each summand in step 2.1 equals $1\mathrm{/}\left(\genfrac{}{}{0px}{}{n}{\mathrm{\mid }S\mathrm{\mid }}\right)$. Substitution yields the asserted LYM inequality.

Fix $S\in [A{]}^k$. Since $A$ is the disjoint union of $S$ and $A\setminus S$, [L1] gives $\mathrm{\mid }A\setminus S\mathrm{\mid }=n-k$. The map $x\mapsto S\cup \{x\}$ is a bijection from $A\setminus S$ to the $(k+1)$-subsets of $A$ properly containing $S$: its inverse sends such a set to its unique element outside $S$. Thus every $S\in [A{]}^k$ has exactly $n-k$ one-element extensions.

Fix $T\in [A{]}^{k+1}$. The map $y\mapsto T\setminus \{y\}$ is a bijection from $T$ to its $k$-element subsets, with inverse sending a $k$-subset to its unique omitted element. Hence $T$ has exactly $k+1$ such subsets.

Count pairs $(S,T)$ with $S\in \mathcal{F}$, $T\in [A{]}^{k+1}$, and $S\subset T$. By step 1.1, there are $\mathrm{\mid }\mathcal{F}\mathrm{\mid }(n-k)$ pairs.

Every second coordinate lies in $\mathrm{\nabla }\mathcal{F}$, and step 1.2 shows that a fixed $T\in \mathrm{\nabla }\mathcal{F}$ contains at most $k+1$ members of $\mathcal{F}$. Thus the same number of pairs is at most $\mathrm{\mid }\mathrm{\nabla }\mathcal{F}\mathrm{\mid }(k+1)$.

Steps 2.1 and 2.2 give $\mathrm{\mid }\mathcal{F}\mathrm{\mid }(n-k)\le \mathrm{\mid }\mathrm{\nabla }\mathcal{F}\mathrm{\mid }(k+1)$. Using [L2] and dividing by the positive binomial coefficients gives the stated normalized inequality.

Equality in step 2.2 holds precisely when every $T\in \mathrm{\nabla }\mathcal{F}$ contributes all of its $k+1$ possible $k$-subsets, which is precisely the equality condition in the Statement.

Therefore the normalized local LYM inequality holds, with the asserted equality characterization.

The symmetry $\left(\genfrac{}{}{0px}{}{n}{k}\right)=\left(\genfrac{}{}{0px}{}{n}{n-k}\right)$ is the symmetry clause of [L1].

For $k<n$, count pairs $(S,x)$ with $\mathrm{\mid }S\mathrm{\mid }=k$ and $x\mathrm{\notin }S$ by first choosing $S$, or by first choosing the $(k+1)$-set $S\cup \{x\}$ and then the deleted element. This gives $\left(\genfrac{}{}{0px}{}{n}{k}\right)(n-k)=\left(\genfrac{}{}{0px}{}{n}{k+1}\right)(k+1)$, in agreement with [L1].

Since both $n-k$ and $k+1$ are positive, step 1.2 shows that $\left(\genfrac{}{}{0px}{}{n}{k+1}\right)\ge \left(\genfrac{}{}{0px}{}{n}{k}\right)$ exactly when $n-k\ge k+1$, with equality exactly when $n-k=k+1$.

Reading step 2.1 as $k$ increases gives strict increase before the middle, equality between the two middle ranks only when $n$ is odd, and strict decrease afterward; symmetry from step 1.1 identifies the stated maximizing ranks.

Put $M:=\left(\genfrac{}{}{0px}{}{n}{\lfloor n\mathrm{/}2\rfloor }\right)$. By [L2], every $\left(\genfrac{}{}{0px}{}{n}{\mathrm{\mid }S\mathrm{\mid }}\right)\le M$, so [L1] gives $\mathrm{\mid }\mathcal{F}\mathrm{\mid }\mathrm{/}M\le {\sum }_{S\in \mathcal{F}}1\mathrm{/}\left(\genfrac{}{}{0px}{}{n}{\mathrm{\mid }S\mathrm{\mid }}\right)\le 1$. Hence $\mathrm{\mid }\mathcal{F}\mathrm{\mid }\le M$.

If equality holds, then every member of $\mathcal{F}$ lies on a rank whose binomial coefficient equals $M$; otherwise the first inequality in step 1.1 would be strict.

If $n$ is even, [L2] leaves only rank $n\mathrm{/}2$. Thus $\mathcal{F}\subseteq [A{]}^{n\mathrm{/}2}$, and equality of cardinalities forces $\mathcal{F}=[A{]}^{n\mathrm{/}2}$.

Suppose $n=2k+1$ is odd. Write $\mathcal{G}:=\mathcal{F}\cap [A{]}^k$ and $\mathcal{H}:=\mathcal{F}\cap [A{]}^{k+1}$. Since $\mathcal{F}$ is an antichain, $\mathcal{H}$ is disjoint from $\mathrm{\nabla }\mathcal{G}$. The two middle levels both have cardinality $M$, and [L3] gives $\mathrm{\mid }\mathrm{\nabla }\mathcal{G}\mathrm{\mid }\ge \mathrm{\mid }\mathcal{G}\mathrm{\mid }$. Therefore $\mathrm{\mid }\mathcal{F}\mathrm{\mid }=\mathrm{\mid }\mathcal{G}\mathrm{\mid }+\mathrm{\mid }\mathcal{H}\mathrm{\mid }\le \mathrm{\mid }\mathcal{G}\mathrm{\mid }+M-\mathrm{\mid }\mathrm{\nabla }\mathcal{G}\mathrm{\mid }\le M$.

Equality in step 3.2 forces $\mathrm{\mid }\mathrm{\nabla }\mathcal{G}\mathrm{\mid }=\mathrm{\mid }\mathcal{G}\mathrm{\mid }$ and $\mathcal{H}=[A{]}^{k+1}\setminus \mathrm{\nabla }\mathcal{G}$. By the equality clause of [L3], whenever $S\in \mathcal{G}$, $x\mathrm{\notin }S$, and $y\in S$, the set $(S\setminus \{y\})\cup \{x\}$ also lies in $\mathcal{G}$: it is a $k$-subset of $S\cup \{x\}\in \mathrm{\nabla }\mathcal{G}$.

Any two $k$-subsets can be joined by repeatedly replacing an element not in the target by an element of the target not yet present. Thus the closure in step 4.1 implies that $\mathcal{G}$ is either empty or all of $[A{]}^k$. In the first case equality forces $\mathcal{H}=[A{]}^{k+1}$; in the second, $\mathrm{\nabla }\mathcal{G}=[A{]}^{k+1}$ and equality forces $\mathcal{H}=\mathrm{\varnothing }$.

Complete levels are antichains and the middle ones have cardinality $M$. Steps 3.1 and 5.1 therefore give all equality cases and complete the proof.

Take one chain $C:S_r\subset S_{r+1}\subset \cdots \subset S_{n-r}$ of the given decomposition, where the subscripts are ranks and $r+(n-r)=n$.

Construct the chain $C_0:S_r\subset S_{r+1}\subset \cdots \subset S_{n-r}\subset S_{n-r}\cup \{x\}$ in $B(A\cup \{x\})$. Its endpoint ranks are $r$ and $n-r+1$, whose sum is $n+1$.

If $r<n-r$, also construct $C_1:S_r\cup \{x\}\subset S_{r+1}\cup \{x\}\subset \cdots \subset S_{n-r-1}\cup \{x\}$. Its endpoint ranks are $r+1$ and $n-r$, whose sum is $n+1$; when $r=n-r$, this second chain is empty and is omitted.

The chains $C_0$ and $C_1$ partition the two copies $\{T:T\in C\}$ and $\{T\cup \{x\}:T\in C\}$: the top set with $x$ goes to $C_0$, and every other set with $x$ goes to $C_1$.