Prove $\operatorname{height}(P) \cdot \operatorname{width}(P) \geq |A|$ in partially ordered set?

Question

Let $P = (A, \preceq)$ be a poset.

Problem: Use Mirsky’s theorem to show $$\operatorname{height}(P) \cdot \operatorname{width}(P) \geq |A|.$$

Please Note: Mirsky's Theorem is

$\text{maximum size of a chain cover} = \text{minimum size of an anti chain}$

My approach:

If we partition $A$ into $k$ anti-chains, $A = A_1 \cup A_2 \cup A_3 \cup \cdots\cup A_k$.

Then, there exists

$$|A_i| \geq \frac{|A|}{\operatorname{height}(P)}$$
I'm not sure this is correct and how do we come up with the width and height formula above?

Answer 1

Let me start to call your attention to the fact that your formulation of Mirsky's Theorem is wrong.
Here's what Wikipedia says about it:

Mirsky's theorem states that, for every finite partially ordered set, the height also equals the minimum number of antichains (subsets in which no pair of elements are ordered) into which the set may be partitioned.

Notice that it could never be something like minimun size of an anti-chain, since that is always $1$ (or $0$, if your definition allows it).

---

So suppose $\mathrm{height}(P)=n$, and $\{A_1, \ldots, A_n\}$ is a partition of $P$ in which each $A_i$ is an anti-chain.
Each anti-chain has at most as many elements has $\mathrm{width}(P)$, by definition of width of a poset. So $$|P| = \sum_{i=1}^n|A_i| \leq n\cdot\mathrm{width}(P)=\mathrm{height}(P)\cdot\mathrm{width}(P).$$