A note on high-dimensional discrepancy of subtrees
Hollom L, Lichev L, Mond A, Portier J. 2026. A note on high-dimensional discrepancy of subtrees. Discrete and Computational Geometry.
Download (ext.)
Journal Article
| Epub ahead of print
| English
Scopus indexed
Author
Hollom, Lawrence;
Lichev, LyubenISTA;
Mond, Adva;
Portier, Julien
Department
Abstract
For a tree T and a function f:E(T)→Sd, the imbalance of a subtree T′⊆T is given by |∑e∈E(T′)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.
Publishing Year
Date Published
2026-10-09
Journal Title
Discrete and Computational Geometry
Publisher
Springer
Acknowledgement
The authors would like to thank both Béla Bollobás and the anonymous reviewer for their careful readings of the manuscript and for their valuable comments. The first author was funded by Trinity College, Cambridge. The second author was funded in whole or in part by the Austrian Science Fund (FWF) 10.55776/ESP624. The third author was supported by UK Research and Innovation grant MR/W007320/2. The fourth author was funded by EPSRC (Engineering and Physical Sciences Research Council) and by the Cambridge Commonwealth, European and International Trust.
ISSN
eISSN
IST-REx-ID
Cite this
Hollom L, Lichev L, Mond A, Portier J. A note on high-dimensional discrepancy of subtrees. Discrete and Computational Geometry. 2026. doi:10.1007/s00454-025-00790-x
Hollom, L., Lichev, L., Mond, A., & Portier, J. (2026). A note on high-dimensional discrepancy of subtrees. Discrete and Computational Geometry. Springer. https://doi.org/10.1007/s00454-025-00790-x
Hollom, Lawrence, Lyuben Lichev, Adva Mond, and Julien Portier. “A Note on High-Dimensional Discrepancy of Subtrees.” Discrete and Computational Geometry. Springer, 2026. https://doi.org/10.1007/s00454-025-00790-x.
L. Hollom, L. Lichev, A. Mond, and J. Portier, “A note on high-dimensional discrepancy of subtrees,” Discrete and Computational Geometry. Springer, 2026.
Hollom L, Lichev L, Mond A, Portier J. 2026. A note on high-dimensional discrepancy of subtrees. Discrete and Computational Geometry.
Hollom, Lawrence, et al. “A Note on High-Dimensional Discrepancy of Subtrees.” Discrete and Computational Geometry, Springer, 2026, doi:10.1007/s00454-025-00790-x.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
arXiv 
Google Scholar