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

96 Views Asked by At

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.

1

There are 1 best solutions below

5
On

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 ;-)