A note on high-dimensional discrepancy of subtrees
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916509157163008 |
|---|---|
| author | Hollom, Lawrence Lichev, Lyuben Mond, Adva Portier, Julien |
| author_facet | Hollom, Lawrence Lichev, Lyuben Mond, Adva Portier, Julien |
| contents | For a tree $T$ and a function $f \colon E(T)\to \mathbb{S}^d$, the imbalance of a subtree $T'\subseteq T$ is given by $|\sum_{e \in 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_04170 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A note on high-dimensional discrepancy of subtrees Hollom, Lawrence Lichev, Lyuben Mond, Adva Portier, Julien Combinatorics For a tree $T$ and a function $f \colon E(T)\to \mathbb{S}^d$, the imbalance of a subtree $T'\subseteq T$ is given by $|\sum_{e \in 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. |
| title | A note on high-dimensional discrepancy of subtrees |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2412.04170 |