A note on high-dimensional discrepancy of subtrees

Abstract

For a tree $T$ and a function $f:E(T)\to {\mathbb{S}}^d$, the imbalance of a subtree $T^{\prime }\subseteq T$ is given by $|{\sum }_{e\in E(T^{\prime })}f(e)|$. The $d$-dimensional discrepancy of the tree $T$ is the minimum, over all functions $f$ as above, of the maximum imbalance of a subtree of $T$. We prove tight asymptotic bounds for the discrepancy of a tree $T$, confirming a conjecture of Krishna, Michaeli, Sarantis, Wang and Wang. We also settle a related conjecture on oriented discrepancy of subtrees by the same authors.

8 pages