Discrepancies of Subtrees

We study multicolour, oriented and high-dimensional discrepancies of the set of all subtrees of a tree. As our main result, we show that the r-colour discrepancy of the subtrees of any tree is a linear function of the number of leaves \(\ell \) of that tree. More concretely, we show that it is bounded by \(\left\lceil {(r-1)\ell /r}\right\rceil \) from below and \(\left\lceil {(r-1)\ell /2}\right\rceil \) from above, and that these bounds are asymptotically sharp. Motivated by this result, we introduce natural notions of oriented and high-dimensional discrepancies and prove bounds for the corresponding discrepancies of the set of all subtrees of a given tree as functions of its number of leaves.