[Math] Maximum size of a poset chain

discrete mathematicselementary-set-theorygraph theory

Let $m,n \geq 2$. Consider the poset $(\{1,…,m\}\times \{1,…,n\}, \rho)$ where $\rho $ is defined by $(i,j)\rho (k,l)$ if and only if $i \leq k$ and $j \leq l$.

What is the maximum size of a chain in this poset? What is the maximum size of an antichain in this poset?

I know that the maximum size would be include finding the size of minimum to the maximum or highest up maximal element. As for the antichain, it would be finding the size of max element to second highest up maximal element.
Any tips?!

Best Answer

  1. length of the longest chain: $m+n-1$
  2. length of the longest antichain: $min\{m,n\}$

The poset is graded or ranked (via $f:(a,b)\to a+b$). Equivalently, every maximal chain has same length. example of a chain: $(1,1)\to (1,2)\to \dots \to (1,n)\to (2,n)\to (3,n)\to \dots \to (m,n)$.

The length of the antichain the largest whitney number (number of elements with a particular rank).

PS: Writing down the hasse diagram is the best way to get the idea. Although, I have used the facts about 'graded' poset, they easy to prove once the definition is known.