4
$\begingroup$

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$.

$\endgroup$

2 Answers 2

8
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ @Jan In Richards book, you will see that this has a close connection to counting lattice points in polytopes as well. Your question is closely connected to finding the Ehrhart polynomial of the poset which is the boolean lattice. I recall (but I am not sure of the source) that this is not known, and even the volume of this polytope is not known exactly. $\endgroup$ Nov 19, 2015 at 1:33
0
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.