Return to Question

Let $T$ be a rooted tree with $m$ leaves. Label every edge with a label of the form $x_i$ or $-x_i$, for some letter $x_i$. For each leaf in the tree, consider the formal linear combination $v$ obtained by summing the labels in the edges from the root to the leaf. What can we say about the dimension of the space $V$ spanned by such $v$?

If all $x_i$'s are distinct, then clearly $\dim V = m$. Say that each $x_i$ appears at most $k$ times. Can one then say that $\dim V \geq m/k - r$, where $r$ is the maximal number of disjoint paths of length $>0$ in the tree such that no inner node of any path is an ancestor of any vertex in any other path?

Let $T$ be a rooted tree with $m$ leaves. Label every edge with a label of the form $x_i$ or $-x_i$, for some letter $x_i$. For each leaf in the tree, consider the formal linear combination $v$ obtained by summing the labels in the edges from the root to the leaf. What can we say about the dimension of the space $V$ spanned by such $v$?

If all $x_i$'s are distinct, then clearly $\dim V = m$. Say that each $x_i$ appears at most $k$ times. Can one then say that $\dim V \geq m/k - r$, where $r$ is the maximal number of disjoint paths in the tree such that (a) no inner node of any path is an ancestor of any vertex in any other path, (b) in every path, there is a letter appearing at least twice?

Let $T$ be a rooted tree with $m$ leaves. Label every edge with a label of the form $x_i$ or $-x_i$, for some letter $x_i$. For each leaf in the tree, consider the formal linear combination $v$ obtained by summing the labels in the edges from the root to the leaf. What can we say about the dimension of the space $V$ spanned by such $v$?

If all $x_i$'s are distinct, then clearly $\dim V = m$. Say that each $x_i$ appears at most $k$ times. Can one then say that $\dim V \geq m/k - r$, where $r$ is the maximal number of disjoint paths from the root to $r$ leaves each with $v=0$?

Let $T$ be a rooted tree with $m$ leaves. Label every edge with a label of the form $x_i$ or $-x_i$, for some letter $x_i$. For each leaf in the tree, consider the formal linear combination $v$ obtained by summing the labels in the edges from the root to the leaf. What can we say about the dimension of the space $V$ spanned by such $v$?

If all $x_i$'s are distinct, then clearly $\dim V = m$. Say that each $x_i$ appears at most $k$ times. Can one then say that $\dim V \geq m/k - r$, where $r$ is the maximal number of disjoint paths of length $>0$ in the tree such that no inner node of any path is an ancestor of any vertex in any other path?

Let $T$ be a rooted tree with $m$ leaves. Label every edge with a label of the form $x_i$ or $-x_i$, for some letter $x_i$. For each leaf in the tree, consider the formal linear combination $v$ obtained by summing the labels in the edges from the root to the leaf. What can we say about the dimension of the space $V$ spanned by such $v$?

If all $x_i$'s are distinct, then clearly $\dim V = m$. Say that each $x_i$ appears at most $k$ times. Can one then say that $\dim V \geq m/k - 1$? If no $v$ as above equals $0$, can one say that $\dim V \geq m/k$?

Let $T$ be a rooted tree with $m$ leaves. Label every edge with a label of the form $x_i$ or $-x_i$, for some letter $x_i$. For each leaf in the tree, consider the formal linear combination $v$ obtained by summing the labels in the edges from the root to the leaf. What can we say about the dimension of the space $V$ spanned by such $v$?

If all $x_i$'s are distinct, then clearly $\dim V = m$. Say that each $x_i$ appears at most $k$ times. Can one then say that $\dim V \geq m/k - r$, where $r$ is the maximal number of disjoint paths from the root to $r$ leaves each with $v=0$?