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,\ldots,|P|\}$.

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,\ldots,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,\ldots,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 $|P|$.

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=|A|$ 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\ge1$, 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\ge1$, 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\ge2$.

On the index set $\{0,\ldots,N-1\}$ define $i\preceq j$ when $i\le j$ and $a_i\le a_j$. The relation is reflexive and transitive componentwise, while $i\preceq j\preceq 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,\ldots,a_n)$ of $A$ determines the maximal chain $\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 $\binom nk$ 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}|S|!(n-|S|)!$.

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}|S|!(n-|S|)!/n!\le1$.

By [L2], each summand in step 2.1 equals $1/\binom n{|S|}$. 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 $|A\setminus S|=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 $|\mathcal F|(n-k)$ pairs.

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

Steps 2.1 and 2.2 give $|\mathcal F|(n-k)\le|\nabla\mathcal F|(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\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 $\binom nk=\binom n{n-k}$ is the symmetry clause of [L1].

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

Since both $n-k$ and $k+1$ are positive, step 1.2 shows that $\binom n{k+1}\ge\binom nk$ 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:=\binom n{\lfloor n/2\rfloor}$. By [L2], every $\binom n{|S|}\le M$, so [L1] gives $|\mathcal F|/M\le\sum_{S\in\mathcal F}1/\binom n{|S|}\le1$. Hence $|\mathcal F|\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/2$. Thus $\mathcal F\subseteq[A]^{n/2}$, and equality of cardinalities forces $\mathcal F=[A]^{n/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 $\nabla\mathcal G$. The two middle levels both have cardinality $M$, and [L3] gives $|\nabla\mathcal G|\ge|\mathcal G|$. Therefore $|\mathcal F|=|\mathcal G|+|\mathcal H|\le|\mathcal G|+M-|\nabla\mathcal G|\le M$.