Lagmental Vicfred

Dilworth Decomposes a Poset by Its Width by Vicfred

Last updated: Mon 01 March 2021

tags: mathematics, posets, Mobius functions, extremal set theory

The maximum antichain size equals the minimum number of chains covering a finite poset. A small computation will anchor the general statement before the abstraction takes over.

Set-up

A finite poset \((P,\le)\) has intervals \([x,y]\) and an incidence algebra. Chains, antichains, and order ideals reveal different slices of its comparability structure.

$$ w(P)=\max\{|A|:A\text{ an antichain}\} $$

The definition determines which expressions are legal; only then does the identity become meaningful. An equality in \(\mathcal A\) may change ambient meaning, so I keep \(\mathsf D\) separate from \(\mathsf C\).

$$ w(P)=\min\{r:P=C_1\cup\cdots\cup C_r,\ C_i\text{ chains}\} $$

The calculation

The middle display is intentionally dense: it is where signs, bounds, multiplicities, or normalising factors are most likely to be lost.

$$ \begin{array}{c|c}\text{poset invariant}&\text{dual covering}\\\hline\text{width}&\text{minimum chain cover}\\\text{height}&\text{minimum antichain cover}\end{array} $$

What survives abstraction

What survives the example is not its particular numbers but the relation encoded by the two rows below. That relation is the part worth transporting to a new setting.

$$ \begin{aligned} \mathsf{D}\;&:\quad w(P)=\max\{|A|:A\text{ an antichain}\},\\[5pt] \mathsf{C}\;&:\quad w(P)=\min\{r:P=C_1\cup\cdots\cup C_r,\ C_i\text{ chains}\}. \end{aligned} $$

The boundary

Width and height refer to antichains and chains in the poset, not to geometric dimensions of a drawing.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] w(P)=\min\{r:P=C_1\cup\cdots\cup C_r,\ C_i\text{ chains}\} \end{gathered}} $$

With the dependency made explicit, the same pattern can be recognised safely in nearby problems. A changed hypothesis should now be easy to spot.

This article was posted on Fri 10 October 2014. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.