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?

  • $\begingroup$ What if $k=2$ and the tree consists of many disjoint paths from the root to the leafs of length 2? The sums may all vanish. $\endgroup$ – Fedor Petrov Jan 23 at 15:55
  • $\begingroup$ You are right; let me amend the question. (The new version is just as good for what I have in mind, and deals with your objection.) $\endgroup$ – H A Helfgott Jan 23 at 15:57
  • $\begingroup$ add an extra edge from a new root to the old root in the above example $\endgroup$ – Fedor Petrov Jan 23 at 16:10
  • $\begingroup$ Brrr :). Well, I can still deal with that, but let me think of something more general that I can also deal with. $\endgroup$ – H A Helfgott Jan 23 at 16:59
  • $\begingroup$ All right, perhaps this will do. $\endgroup$ – H A Helfgott Jan 23 at 17:18

The following is a (partial self-)answer both in the positive and in the negative direction.

Lemma A. Assume that there are at least $n$ distinct non-zero values of $v$, i.e., $n$ leaves whose corresponding $v$'s are all non-zero and distinct. Then $\dim V \geq n/k$.

This Lemma follows from Lemma B below; just prune leaves whose $v$ appears as the $v$ of some other leaf until no such repetitions are left, and orient all edges of $T$ away from the root, thus making $T$ into a directed graph. (Actually, let me denote $v$ by $u$ from some on, so that there is no confusion with the use of $v$ to denote a vertex.)

In a directed graph whose edges have labels of the form $\pm x$, we associate a formal linear combination of letters $u(\phi)$ to a (directed) path $\phi$ in the obvious way: edges traversed against their orientation in a path are counted with their signs flipped.

Lemma B. Let $\Gamma$ be a connected, oriented graph where every edge has a label of the form $x$ or $-x$ for some letter $x$. Assume that every letter appears in at most $k$ labels. Let $S$ be a set of $n$ vertices in $\Gamma$. Assume that, for every pair of distinct elements $v, v'\in S$, any path $\phi$ from $v$ to $v'$ satisfies $u(\phi)\ne 0$. Then the space $V$ spanned by all such paths has dimension $\geq (n-1)/k$.

Proof of Lemma B.- Let $v, v'$ be any two distinct elements of $S$. Let $\phi_1$ be a path from $v$ to $v'$. Choose any edge $e$ in $\phi_1$, and say that its label is $x$ or $-x$. Now remove from $\Gamma$ every edge with the label $x$ or $-x$. We obtain a graph with at most $k+1$ connected components (some of them possibly consisting of a single vertex). Choose any connected component containing at least two distinct elements of $S$, and iterate: let $\phi_2$ be a path from one to the other, etc.

After $r$ steps, we have a graph with $\leq r k + 1$ connected components. We stop when there is no connected component containing at least two elements of $S$; that can happen only if $r k + 1 \geq n$, i.e., only if $k\geq (n-1)/r$. We have paths $\phi_1,\phi_2,\dotsc,\phi_r$ such that, for every $1\leq i\leq r$, there is a letter $x$ appearing in $u(\phi_i)$ but absent from $u(\phi_{i'})$ for all $i<i'\leq r$. Hence the span $\langle u(\phi_1),u(\phi_2),\dotsc,u(\phi_r)\rangle$ is $r$-dimensional.

End of Proof of Lemma B.

Now, the problem in applying Lemma A to my original question resides simply in that there may not be many distinct non-zero values of $v$. In fact, it could be that $v$ is the same for all the leaves for a tree with $2^m$ leaves and height $2 m$, and yet $k=2$. (For instance, for $m=2$, let $T$ be a tree with paths from the root to the leaves given by abcd, abdc, cdab, cdba, with branching in the natural way: the edges containing to the root are labelled a and c, those edges lead to edges b and d, those fork out into c and d and into a and b, respctively, etc.) It may be that $r$ is always large for such examples, but it might not be; perhaps someone wants to construct a counterexample to my original question with low $r$?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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