---
OA_place: repository
OA_type: green
_id: '23158'
abstract:
- lang: eng
  text: 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.
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.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Lawrence
  full_name: Hollom, Lawrence
  last_name: Hollom
- first_name: Lyuben
  full_name: Lichev, Lyuben
  id: 9aa8388e-d003-11ee-8458-c4c1d7447977
  last_name: Lichev
- first_name: Adva
  full_name: Mond, Adva
  last_name: Mond
- first_name: Julien
  full_name: Portier, Julien
  last_name: Portier
citation:
  ama: Hollom L, Lichev L, Mond A, Portier J. A note on high-dimensional discrepancy
    of subtrees. <i>Discrete and Computational Geometry</i>. 2026. doi:<a href="https://doi.org/10.1007/s00454-025-00790-x">10.1007/s00454-025-00790-x</a>
  apa: Hollom, L., Lichev, L., Mond, A., &#38; Portier, J. (2026). A note on high-dimensional
    discrepancy of subtrees. <i>Discrete and Computational Geometry</i>. Springer.
    <a href="https://doi.org/10.1007/s00454-025-00790-x">https://doi.org/10.1007/s00454-025-00790-x</a>
  chicago: Hollom, Lawrence, Lyuben Lichev, Adva Mond, and Julien Portier. “A Note
    on High-Dimensional Discrepancy of Subtrees.” <i>Discrete and Computational Geometry</i>.
    Springer, 2026. <a href="https://doi.org/10.1007/s00454-025-00790-x">https://doi.org/10.1007/s00454-025-00790-x</a>.
  ieee: L. Hollom, L. Lichev, A. Mond, and J. Portier, “A note on high-dimensional
    discrepancy of subtrees,” <i>Discrete and Computational Geometry</i>. Springer,
    2026.
  ista: Hollom L, Lichev L, Mond A, Portier J. 2026. A note on high-dimensional discrepancy
    of subtrees. Discrete and Computational Geometry.
  mla: Hollom, Lawrence, et al. “A Note on High-Dimensional Discrepancy of Subtrees.”
    <i>Discrete and Computational Geometry</i>, Springer, 2026, doi:<a href="https://doi.org/10.1007/s00454-025-00790-x">10.1007/s00454-025-00790-x</a>.
  short: L. Hollom, L. Lichev, A. Mond, J. Portier, Discrete and Computational Geometry
    (2026).
das_tickbox: '1'
dataavailabilitystatement: Data sharing not applicable to this article as no datasets
  were generated or analysed during the current study.
date_created: 2026-10-18T22:01:53Z
date_published: 2026-10-09T00:00:00Z
date_updated: 2026-10-19T08:20:42Z
day: '09'
department:
- _id: MaKw
doi: 10.1007/s00454-025-00790-x
external_id:
  arxiv:
  - '2412.04170'
fulldoi: https://doi.org/10.1007/s00454-025-00790-x
keyword:
- Trees
- High-dimensional discrepancy
- Oriented discrepancy
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2412.04170
mathsc:
- 05C05
- 05C35
- 11K38
month: '10'
oa: 1
oa_version: Preprint
project:
- _id: e19fef4c-1f3d-11f0-ac04-b8b1af6886d8
  grant_number: E624
  name: THRESHOLDS IN SEMI-RANDOM PROCESSES AND GRAPH EMBEDDINGS
publication: Discrete and Computational Geometry
publication_identifier:
  eissn:
  - 1432-0444
  issn:
  - 0179-5376
publication_status: epub_ahead
publisher: Springer
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: A note on high-dimensional discrepancy of subtrees
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2026'
...