# Number of upper sets of size $n$ in a finite tree

Consider a finite tree $T = (V, <)$, where $y < x$ means that $y$ is the parent of $x$. We assume that $T$ has a unique root $r$ that has no parent. An upper set of $T$ is a subset $S$ of $V$ such that for any $x \in S$, any $y \in V$ such that $y < x$ (i.e., $y$ is an ancestor of $x$) is also in $S$. Consider $f_T : \mathbb{N} \rightarrow \mathbb{N}$ the function associating to $k$ the number of upper sets of $T$ of size $k$, i.e., $f_T : k \mapsto \left|\left\{S \mathrm{\,upper\,set\,of\,} X \mid |S| = k\right\}\right|$. Clearly $f_X(0) = 1$ (with $S = \emptyset$), $f_X(1) = 1$ (with $S = \{r\}$), $f_X(|V|) = 1$ (with $S = V$), and $f_T(k) = 0$ iff $k > |V|$.

On simple examples it seems that $f_T$ increases from $1$ to some maximal value $m$ and then decreases back to $1$, i.e., it has no local minima. Is this property true for any choice of $T$?

(Note that this property does not hold for general partial orders, which is why I restrict the question to trees.)

Edit: The proper terminology is that the upper sets of $X$ form a distributive lattice that is known to be ranked (or graded); the $f_X$ are the Whitney numbers of this lattice. The property that we want to prove is that this lattice is rank-unimodal.

-

Let consider a tree induced on $T = \{1,3,9,27,2,4,8,16,32,64\}$ by relation of divisibility, where $1$ is the root. Let $L = \{1, 2, 4, 8, 16, 32, 64\}$ be left branch and $R = \{1, 3, 9, 27\}$ the right one. $L$ is independent of $R$, so $f_L = 1\cdot\chi_{\{0,1,2,3,\ldots, 7\}}$ and $f_R = 1\cdot\chi_{\{0,\ldots,4\}}$, but observe, that $f_T$ is almost their convolution: $$f_T(k) \sim \sum_{i} f_L(i)\cdot f_R(k-i).$$
The only problem is that the root belongs to both $L$ and $R$. I think it is possible to do an induction over the structure of the tree "adding" new branches and "almost convoluting" the subtrees functions. Intuition tells me the result would be just as you describe, a function that increases and then decreases.
Thanks for this remark. In fact, I'm already aware of the following result: for any binary tree $T$ with root subtrees $L$ and $R$ (not just the divisibility example you gave), we have $f_T(k) = \sum_i f_L(i) f_R(k-i-1)$. (Any upper set of size $i$ in $T$ is obtained by taking one upper set in $L$ and one in $R$, with all possible repartitions of sizes.) This generalizes to trees of arbitrary arity, and, indeed, it's a convolution. However, I can't manage to do an induction from here. I'm not sure if we don't need a stronger induction hypothesis that the result I conjectured. – a3nm Feb 4 '13 at 16:20
Yes, you can indeed show by induction on the tree $T$ that $f_T$ is log-concave. Thanks a lot for pointing me to this, I believe this was the right notion needed for the induction hypothesis. If you edit your answer to mention this, I'll accept it. – a3nm Feb 6 '13 at 8:13