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 $\mathrm{\ell }$ of that tree. More concretely, we show that it is bounded by $\lceil (r-1)\mathrm{\ell }\mathrm{/}r\rceil$ from below and $\lceil (r-1)\mathrm{\ell }\mathrm{/}2\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.