Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

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.

I know this is barely a sketch, but I hope it helps ;-)

share|improve this answer
    
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
    
The divisibility was just a short way of providing an example (and as I remember, any finite tree can be represented in terms of divisibility). What do you need more than: a convolution of two "mountains" is again a "mountain"? –  dtldarek Feb 4 '13 at 16:25
    
If it is indeed true that the convolution of two "mountains" is indeed a "mountains", then the result is proved and I'm happy, but in fact I'm not sure this is always true. –  a3nm Feb 4 '13 at 16:28
    
It is not, but convolution of two log-concave functions is again log-concave, and characteristic function of convex sets are log-concave. This should be enough, right? –  dtldarek Feb 4 '13 at 18:30
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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