Is there a short expression for height and width of product and coproduct of posets?

Question

I am trying to derive some basic relations for the height and width of the direct product and the coproduct of posets. I feel that these are very basic and should be written somewhere, however, I cannot find a reference.

Short question is: is there a short expression for the following quantities, representing height and width of product and coproduct of posets? And do they hold also in the case of infinite cardinality?

Edit: current status (with help from Harry Altman, David Spivak) of this question:

[resolved] $\color{green}{ w(P\coprod Q) = w(P)+w(Q) }$

[resolved] $\color{green}{ h(P\coprod Q) = \max\{h(P), h(Q)\}}$

[resolved] Assuming $P$ and $Q$ not empty, then $\color{green} {h(P \times Q) = h(P)+h(Q)−1 }$. (For empty posets, then $h(P \times Q) = 0 \neq h(P)+h(Q)-1$.)

[resolved] From a theorem in Berzukov, Roberts, "On antichains in product posets", it follows that the width can be bounded as follows, with both bounds attainable:

$\color{green}{ w(P)w(Q)\leq w(P\times Q) \leq \min\{|P|\ w(Q), |Q|\ w(P)\}} $

Original question below.

---

Preliminaries Define:

• $C_n$ to be a chain of size $n$. For example take $C_n = \langle\{1, \dots, n\}, \leq\rangle$.
• $A_n$ to be an antichain of size $n$, that is, a set with $n$ incomparable elements.
• $P \times Q$ the direct product of two posets.
• $G_{m,n}$ is a grid; for example $G_{m,n} = C_n \times C_m$.

The height and width of a poset are defined as:

• the height $h(P)$ is the cardinality of the longest chain in $P$.
• the width $w(P)$ is the cardinality of the longest antichain in $P$.

Some simple examples:

Width of a chain: $w(C_n) = 1$.

Height of a chain: $h(C_n) = n$.

Width of an antichain: $w(A_n) = n$.

Height of a antichain: $w(A_n) = 1$.

Width of an $m\times n$ grid: $w(G_{m\times n}) = \min\{m,n\}$

Height of an $m\times n$ grid: $w(G_{m\times n}) = m + n -1$

Questions

Is there a simple expression for the height and width of a product and a coproduct of a poset?

This is what I got so far.

For a co-product:

The height must be the maximum of the two heights, because chains belonging to different factors are uncomparable:

$ h( P \coprod Q) = \max\{ h(P), h(Q) \}$

For the width, the widths of the factors sum together:

$ w( P \coprod Q) = h(P) + h(Q) $

This is because I can take an antichain $S_1$ in $P$ and one antichain $S_2$ in Q, and then $S_1\cup S_2$ is an antichain in $P \coprod Q$.

For a product, I am not sure.

For the height of a product I can certainly say that

$h(P\times Q) \geq h(P) + h(Q) - 1$

because I can construct a chain of that size. If $C=\{1,2,\dots,h(P)\}$ is the longest chain in $P$ and $D = \{a,b,\dots\}$ the longest chain in $Q$ then I can construct the chain $E = \{(1,a), (2,a), \dots, (h(P), a), (h(P), b), \dots\}$ that has height $ h(P) + h(Q) - 1$.

I am also not sure if any of the above fails for posets of infinite cardinality.

Answer 1

Sticking first to finite sets, for the question of $h(P\times Q)$, one does in general have $h(P \times Q)=h(P)+h(Q)-1$. You've already proven the lower bound. For the upper bound, take a chain $(a_1,b_1),\ldots,(a_n,b_n)$ in $P\times Q$; let's assume this is written in increasing order. (Note this is strictly increasing.) Then each time we go from $(a_i,b_i)$ to $(a_{i+1},b_{i+1})$, at least one of the coordinates must increase (the other is allowed to stay the same). But the first coordinate can only increase $h(P)-1$ times, and the second only $h(Q)-1$ times. So the total number of elements in the chain is at most $(h(P)-1)+(h(Q)-1)+1=h(P)+h(Q)-1$.

If you want to generalize with infinite posets, you should make sure you know exactly what definitions you want to work with -- is it really cardinality that you want to look at? I suppose for $w(P)$ you'd have to just use cardinality, as I don't think there's really any other good way to measure the "size" of an antichain in a general poset. But for height you can possibly do more. For instance, if you are working with well-founded partial orders, you might want to look at the largest embedded ordinal to get more information.

Note also that in this case your maxima might have to be replaced by suprema; for instance, consider the disjoint union of a chain of length $k$ for every $k$. This has no longest chain!

For well-founded partial orders, the supremum of all embedded ordinals is (I'm pretty sure?) the same as what's generally known as the height of the order in that context. There is actually a similar formula for $\ell(P\times Q)$ in that case but I will come back and edit in later if nobody else has already stated it, I am typing this in a bit of a hurry, sorry.

Edit: Let me also add briefly -- your grid example already shows that there can be no formula for $w(P\times Q)$ in terms of $w(P)$ and $w(Q)$, since there you have $w(P)=w(Q)=1$ but $w(P\times Q)$ arbitrarily large. This can be extended to the infinite realm as well; if you have some given cardinal, take a totally ordered set $X$ of that cardinality, and consider $X\times X'$, where $X'$ is the same set as $X$ but with the reverse order. Then the "diagonal" is an antichain. But maybe you were intending to allow for other quantities in the formula?

(Also, obviously all the coproduct stuff will work for anything infinite, and should continue to unless you are using some very strange definitions.)

Edit: More on the width -- here's an example that shows that $w(P)$, $w(Q)$, $h(P)$, and $h(Q)$ are not enough to determine $w(P\times Q)$. Say $P$ is a poset on three elements, with two elements forming an antichain and the third on top; and say $Q$ is the reverse. Then $w(P)=w(Q)=h(P)=h(Q)=2$, but (if I've done this correctly) $w(P\times P)=4$, while $w(P\times Q)=5$.

As for if one only wants a bound -- well, for a finite set $P$, Dilworth's theorem implies that $|P|\le h(P)w(P)$, and certainly $w(P)\le P$, so one thereby gets the trivial bound $w(P\times Q)\le w(P)w(Q)h(P)h(Q)$. But I rather doubt that's what you wanted... (there is of course also the easy lower bound $w(P\times Q)\ge w(P)w(Q)$).

Also, to handle $h(P\times Q)$ in the infinite case, if we use the definitions you've give above where we just care about cardinality -- if either $h(P)$ or $h(Q)$ is infinite (and neither is zero, see below), then $h(P\times Q)=\max\{h(P),h(Q)\}$. Certainly it is at least this; and it's easy to see that $h(P\times Q)\le h(P)h(Q)$ (since its projection onto either coordinate is a chain). But the product of two nonzero cardinals, at least one of which is infinite, is simply their maximum, answering the question. Of course, you could ask for a solution that works without axiom of choice, and that I do not have at the moment!

Actually, if we want to nitpick, the formula for $h(P\times Q)$, here and in the finite case, has an exception -- if either $h(P)$ or $h(Q)$ is zero, then of course so is $h(P\times Q)$.

Edit: OK, one last edit -- about the well-founded case I mentioned above: We can define the height of an element of a well-founded partial order, it's the least ordinal greater than the heights of all elements less than it; the height of the partial order is then the least ordinal greater than the heights of all the elements. The height is usally denoted $\ell$ in this context so that's what I'll do. Then if you have two WFPOs $X$ and $Y$, and you have $(x,y)\in X\times Y$, then $\ell(x,y)=\ell(x)\oplus\ell(y)$, where $\oplus$ is natural addition.

This means that $\ell(X\times Y)$ is the smallest ordinal greater than any $\alpha\oplus\beta$ for any $\alpha<\ell(X)$ and $\beta<\ell(Y)$. How can we compute this? I'll use the "order" of an ordinal to mean the smallest term that appears in its Cantor normal form. Take the natural sum of $\ell(X)$ and $\ell(Y)$. If $\ell(X)$ has the higher order, drop everything below the lowest term in $\ell(X)$. If $\ell(Y)$ has the higher order, same but with $\ell(Y)$. If the orders are equal, just drop one copy of the lowest term.

So you can see that this genralizes the $h(P\times Q)=h(P)+ h(Q)-1$ that occurs when $P$ and $Q$ are finite and all the terms are $1$.

(And of course again if either of them is zero you get zero.)