What are bounds for the number of monotone functions $M:P\rightarrow T$ where $P$ is a finite poset and $T$ is a finite totally ordered set?

Question

For the case where $P=\{0,1\}^n$ and $T=\{0,1\}$ the number of such functions is called the $n$-th Dedekind number and I discovered that there is large literature on determining bounds for these numbers (I'm not an expert in the field. I work in theoretical economics and stumbled on this question when studying a question in choice theory). So I was wondering about what is known about the generalization posed in my question. In particular, I'm interested in the case where $P=\{1,\ldots,m\}^n$ and $T=\{0,\ldots,m\}$ and bounds as a function of $n$ and $m$.

Answer 1

Let $\Omega_P(m)$ denote the number of monotone functions $P\to \{1,\dots,m\}$. Then $\Omega_P(m)$ is a polynomial in $m$ known as the order polynomial of $P$. For some basic properties see Section 3.15 of my book Enumerative Combinatorics, vol. 1, second ed. Many of the techniques used to bound the case $P=\{0,1\}^n$ and $T=\{0,1\}$ should be applicable to $P=\{1,\dots,m\}^n$ and $T=\{0,\dots,m\}$, though I am not aware of anyone who had tried to do this. The case $n=2$ is quite interesting (part of the theory of plane partitions) and can be done explicitly. An even more general result is Theorem 7.21.7 of Enumerative Combinatorics, vol. 2.

Answer 2

For any $n$, there are upper and lower bounds of the form $\exp (c m^n)$. The constant may depend on $n$ and whether you are looking at an upper vs. lower bound.

Let $[m]$ be any chain on $m$ vertices, say $\{1,...,m\}$. Maps $[m]^n \to [m+1]$ are determined by the chain of $m$ order ideals of $[m]^n$ that are the preimages of $[1],...[m]$. So, they are equivalent to order ideals of $[m]^{n+1}$.

Lower bound: Consider the subset of $[m]^{n+1}$ of all points with coordinate sum less than $a=\lfloor m(n+1)/2 \rfloor$. We can add an arbitrary subset of the $c m^n$ points with coordinate sum $a+1$ to produce distinct order ideals of $[m]^{n+1}$.

Upper bound: For any poset $P$, there is an injection from order ideals of $[m] \times P$ to pairs $(I,S)$ where $I$ is an order ideal of $[\lceil m/2 \rceil]\times P$ and $S \subset P$. To obtain $I$, look at the intersection with $\{2,4,...,2 \lceil m/2 \rceil \} \times P$. Let $p \in S$ when the number of elements of the ideal of the form $(x,p)$ is odd. $(I,S)$ determines each level set $\{x\} \times P$: $I$ determines the even levels, and given that, $S$ lets us reconstruct the odd levels.

Applying this $n+1$ times, to each coordinate in turn, implies that the number of order ideals of $[m]^{n+1}$ is at most $2^{m^n} \times 2^{\lceil m/2 \rceil m^{n-1}} \times ... \times 2^{\lceil m/2 \rceil^{n-1} m} = \exp(c m^n)$ times the number of order ideals of $[\lceil m/2 \rceil]^{n+1}$. Repeating this, we get an upper bound of $\exp cm^n$ with a different constant.

By the way, these bounds together with a covering of the allowed points in the positive orthant by boxes imply that the number of order ideals of $\mathbb{N}^d$ with $n$ elements is bounded above and below by functions of the form $\exp c n^{(d-1)/d}$. Much more specific asymptotics are known for $d\le 3$.