Maximum antichain in a special poset

190 Views Asked by At

Let $A, B, C$ be given natural numbers.

Let us define a poset, on a set $P=\{ (x, y, z) | x, y, z \in \mathbb{N}, 1\le x \le A, 1 \le y \le B, 1 \le z \le C \}$.

For two elements $U=(x_1,y_1,z_1)$ and $V=(x_2,y_2,z_2)$, we say that $U \le V$ if and only if $x_1 \le x_2, y_1 \le y_2, z_1 \le z_2$.

Find the width of this poset.

I thought about this problem for a while, and I thought it was nice enough to ask it here.

1

There are 1 best solutions below

2
On BEST ANSWER

In effect you are asking for the width of the lattice of divisors of the number $2^{A-1}3^{B-1}5^{C-1}$.

A natural number is said to be of degree $m$ if it's the product of $m$ primes. If $N$ is of degree $2m,$ then the largest antichain of divisors of $N$ is the set of all divisors of degree $m.$ If $N$ is of degree $2m+1$, there are two largest antichains of divisors of $N:$ the set of all divisors of degree $m,$ and the set of all divisors of degree $m+1.$ This generalizes Sperner's theorem, which is just the case where $N$ is squarefree.

Example: $N=720=2^4\cdot3^2\cdot5$ is of degree $7.$ The six divisors of degree $3$ are $8,\ 12,\ 18,\ 20,\ 30,\ 45;$ the six divisors of degree $4$ are $16,\ 24,\ 36,\ 40,\ 60,\ 90.$

The reference for this result is:

N. G. de Bruijn, Ca. van Ebbenhorst Tengbergen, and D. Kruyswijk, On the set of divisors of a number, Nieuw Arch. Wiskunde (2) 23 (1951), 191–193.

(Answer plagiarized from this old answer which I posted in a previous life.)