1. Discrepancies of subtrees
- Author
-
Krishna, Tarun, Michaeli, Peleg, Sarantis, Michail, Wang, Fenglin, and Wang, Yiqing
- Subjects
11K38, 05C15, 05C05 ,FOS: Mathematics ,Mathematics - Combinatorics ,Combinatorics (math.CO) - Abstract
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 $\lceil(r-1)\ell/r\rceil$ from below and $\lceil(r-1)\ell/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., Comment: 12 pages
- Published
- 2023
- Full Text
- View/download PDF