# Poset dimension and width (Dilworth's theorem)

For a given poset $$P$$, let $$\mathrm{dim}(P)$$ denote the least cardinal $$\kappa$$ such that there exists a $$\kappa$$-sized collection of linear extensions of $$P$$, say $$\mathcal{L}$$, such that $$\leq_P = \bigcap_{L\in \mathcal{L}}\leq_L$$. Let $$\mathrm{width}(P)$$ denote the least cardinal $$\lambda$$ such that every antichain $$A\subset P$$ has size $$<\lambda$$.

Note that the definition of width here is slightly different from the usual definition seen in combinatorics textbooks but we do this in the set-theoretic convention to deal with the possibility that there is no antichain with maximum cardinality.

Dilworth (https://www.jstor.org/stable/1969503?seq=1#metadata_info_tab_contents) proved that if $$\mathrm{width}(P)$$ is finite, then $$\mathrm{dim}(P)<\mathrm{width}(P)$$. The proof goes through the fact that if the width of $$P$$ is $$k$$, then $$P$$ can be decomposed into a union of $$ many chains. This fact is not true for $$k\geq \aleph_0$$. However, the counter-example (Perles' example https://link.springer.com/article/10.1007%2FBF02759806) has dimension 2 so it satisfies $$\mathrm{dim}(P)<\mathrm{width}(P)$$. Are there examples violating $$\mathrm{dim}(P)<\mathrm{width}(P)$$?

EDIT: Suggested by bof, the width is better defined as the supremum of the sizes of antichains. So with the new definition, Dilworth's theorem states $$\mathrm{dim}(P)\leq \mathrm{width}(P)$$ for $$P$$ of finite width and my question will be modified to whether this is true in general.

For your modified question, namely, does there exist a poset $$P$$ such that $$\dim(P) > \sup \{|A|: A\subset P \text{ is an antichain}\}$$, the answer is positive. Due to Laver (An Order Type Decomposition Theorem, Annals of Mathematics Second Series, Vol. 98, No. 1 (Jul., 1973), pp. 96-119) and in fact he showed that

for any uncountable $$\kappa$$, there exist a poset $$P$$ whose width is $$\aleph_0$$ and dimension is $$\kappa$$.

The poset is the class of scattered linear orders of size $$<\kappa$$ ordered by embeddability (modulo bi-embeddability to make it a poset).

This in some sense is a strengthening of Perles' result.

Let $$P=P_1\cup P_2\cup P_3\cup\cdots$$ where $$P_1\lt P_2\lt P_3\lt\cdots$$, each $$P_n$$ is finite, and $$\dim(P_n)=n$$. Then $$\dim(P)=\operatorname{width}(P)=\aleph_0$$.

More generally, if $$\kappa$$ is a strong limit cardinal, there is a poset $$P$$ with $$\dim(P)=\operatorname{width}(P)=|P|=\kappa$$.

Maybe I should have posted this as a comment rather than an answer. All these examples show is that you're using the wrong definition of "width". Try defining the width naturally, as the supremum of the cardinalities of antichains; and then ask whether there are any counterexamples to $$\dim(P)\le\operatorname{width}(P)$$. I have no idea.

• @MonroeEskew How so? Every two elements of distinct $P_i$ are comparable, so all antichains are finite. – Wojowu Feb 2 '19 at 16:28
• I see. Maybe the question to ask is whether there is $P$ such that $\mathrm{dim}(P)>\mathrm{width}(P)$ ... – Otto Feb 2 '19 at 17:12