A note on high-dimensional discrepancy of subtrees

Adva Mond; Julien Portier; Lawrence Hollom; Lyuben Lichev

REVIEW 3 major objections 4 minor 18 references

A note on high-dimensional discrepancy of subtrees

T0 review · 3 major / 4 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves that the discrepancy of any tree's subtrees is asymptotically $\ell/(d\,B(d/2,1/2))$, confirming the earlier conjecture on tightness.

desk verdict A short, correct-looking proof of the conjectured tight discrepancy for subtrees, with a few localized write-up gaps that a referee should ask to be fixed before publication. read the letter →

arxiv 2412.04170 v1 pith:IDXEGCI3 submitted 2024-12-05 math.CO

Lawrence Hollom , Lyuben Lichev , Adva Mond , Julien Portier This is my paper · ORCID

classification math.CO MSC 05C0505C1511K38

keywords discrepancytheorytreesubtreesspherecoloringsorientedepsilon-netsasymptotictightnessBetafunction

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

For every fixed dimension $d$, the paper proves that any tree with $\ell$ leaves has $d$-dimensional subtree discrepancy $\frac{\ell}{d\,B(d/2,1/2)}(1+o(1))$, where $B$ is the Beta function. This matches a lower bound proved in the earlier paper [15], confirming the conjecture that the lower bound is asymptotically tight. The proof constructs a coloring for stars by random antipodal pairs of vectors on the sphere and then reduces an arbitrary tree to a star forest by pruning leaves whose neighbor has degree two. The same construction settles the oriented version: the oriented discrepancy of subtrees is $(1/2+o(1))\ell$. The constant matters because it gives the exact asymptotic cost of balancing all connected subtrees of a tree simultaneously, and it links vector discrepancy to ordinary color discrepancy through the regular simplex identity.

What carries the argument

Three objects carry the proof. First, the random antipodal star coloring: choose $\lceil \ell/2\rceil$ points $x_i$ uniformly on $\mathbb{S}^d$ and color each leaf by either $x_i$ or $-x_i$; the maximum imbalance of a subtree is controlled by $R_a=\sum_i|\langle x_i,a\rangle|$, whose expectation per pair is $2/(d\,B(d/2,1/2))$, and an $\varepsilon$-net on the sphere turns the supremum over directions $a$ into a finite union bound. Second, Claim 2.3: if a leaf's neighbor has degree two, deleting that leaf edge does not change $D_d$, so every tree can be pruned into a skeleton with no degree-two parents of leaves. Third, the star-forest decomposition: split the pruned tree into a star forest $F$ and a residual tree $R$ whose leaf counts shrink geometrically, apply the star bound to each component, and sum via the triangle inequality.

What would settle it

For $d=2$, the theorem predicts that a star with $\ell$ leaves has discrepancy $(1+o(1))\ell/4$, since $B(1,1/2)=2$. A numerical or exact computation of $\min_f \max_{S'\subseteq S_\ell}\|\sum_{e\in S'} f(e)\|$ for a large $\ell$ that falls below $\ell/4$ by a constant fraction would refute the lower bound, while a value above $\ell/4+O(\ell^{3/4})$ would refute the upper bound.

Watch

Extended reading notes

Core claim

The central discovery is that the lower bound $D_d(T)\ge \ell/(d\,B(d/2,1/2))$ is tight up to a factor $1+o(1)$ for every fixed $d$, so the leaf count is the only asymptotic parameter that controls subtree discrepancy. The paper proves this by establishing the matching upper bound: for stars, $\ell/2$ random antipodal pairs on $\mathbb{S}^d$ make the worst subtree sum at most $\ell/(d\,B(d/2,1/2)) + O(\ell^{3/4})$ with positive probability; for general trees, repeated application of a pruning claim reduces the tree to a star forest with geometrically decaying leaf counts, and summing the star bounds yields the main theorem. The same decomposition, with an oriented pruning claim that loses at most one unit per step, gives $\vec D(T)=(1/2+o(1))\ell$ and settles the second conjecture.

Load-bearing premise

The tightness claim rests on two steps taken as given: the imported lower bound $D_d(T)\ge \ell/(d\,B(d/2,1/2))$, and the pruning equality that deleting a leaf edge from a degree-two neighbor leaves the discrepancy unchanged; the written proof of the pruning step skips the single-edge case.

Editorial extensions

If this is right

The exact constant $\ell/(d\,B(d/2,1/2))$ determines the asymptotic discrepancy for every fixed dimension $d$, so dimension enters only through the Beta factor $B(d/2,1/2)$ and the leaf count is the sole structural parameter.
Because the same pruning works for all trees, the result shows that the asymptotic discrepancy is universal across trees with the same number of leaves; topology beyond leaf count only affects lower-order terms.
Through the regular-simplex identity, the vector bound transfers to $(d+1)$-colourings, giving matching-order bounds on the combinatorial discrepancy of subtrees.
The oriented discrepancy statement $\vec D(T)=(1/2+o(1))\ell$ confirms the second conjecture and shows that an optimal orientation can balance rooted oriented subtrees only up to half the leaf count.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Extrapolating from the method, the star proof actually yields a quantitative error term $O(\ell^{3/4})$; tracking the constants in the $\varepsilon$-net and Chernoff steps could turn the main $o(1)$ statement into an explicit finite-$\ell$ bound.
The pruning decomposition depends only on the degree-two parent structure, so a similar leaf-count-driven constant may hold for forests, or for trees with weighted edges, by summing over components.
If the imported lower bound could be proved directly, the same upper-bound machinery would upgrade the identity from asymptotic to exact at the level of the leading constant; the remaining gap is the black-box lower bound, not the construction.
A natural next target is the second-order term, which the proof suggests should be $O(\ell^{3/4})$ for stars but may depend on the tree's diameter for general trees.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Quick take: this note proves the expected tight asymptotic for subtree discrepancy, ℓ/(d B(d/2,1/2)), and settles the oriented version at ℓ/2. The main ideas—random antipodal pairs, epsilon-nets, leaf-pruning decomposition—are right, and the paper is worth engaging with, but the write-up has a few genuine rough spots. What's new: Theorem 1.2 confirms the conjecture from Krishna et al. for every d, not just d=1; Theorem 1.4 confirms the oriented conjecture. The star lemma is clean: sample ℓ/2 antipodal pairs, union-bound over an epsilon-net, and get the constant from E|| = 2/(d B(d/2,1/2)). The reduction of a general tree to a star forest plus a residual tree with geometrically decaying leaf count is the right structural argument. Soft spots, in proportion. The reader flagged a numerator/denominator typo in the constant, but that does not reproduce in the version I read: Theorem 1.2 has B in the denominator, consistent with the proof. That concern is a false positive. The real issues are smaller. Claim 2.3's proof of equality (5) is not literally correct: for the subtree consisting only of the pendant edge xy, the sum is −f(yz), not what their subtraction of both xy and yz gives. The equality of maxima still holds because {yz} in T' has the same norm, so the claim survives with a sentence added. Claim 2.4 is sketchy—phrases like "one can ensure" and "similarly" carry real weight, and the final induction for Theorem 1.4 is compressed. None of this threatens Theorem 1.2, but a referee should ask for a cleaned version, especially since the paper sells itself as a note. The lower bound is imported from [15, Thm 7]. That is legitimate—it is a published theorem—but the asymptotic tightness is only as solid as that external result. The paper's own star computation independently matches the constant, which is reassuring. Who for: anyone working in combinatorial discrepancy or geometric discrepancy on graphs. It is a note, so do not expect broad impact, but it resolves two open conjectures cleanly. I would send it to a serious referee; with the proof details fixed, it should be publishable.

Referee Report

3 major / 4 minor

Summary. The paper studies the d-dimensional discrepancy of subtrees of a tree T, denoted D_d(T), and the oriented counterpart D⃗(T). Its main result, Theorem 1.2, states that for every tree with ℓ leaves, D_d(T) = (1+o(1)) ℓ/(d B(d/2,1/2)), confirming a conjecture of Krishna, Michaeli, Sarantis, Wang and Wang. The second result, Theorem 1.4, states that D⃗(T) = (1/2+o(1))ℓ, confirming a related conjecture. The upper bound is obtained by a random construction on stars (with an ε-net and concentration arguments), a decomposition of the tree into a star forest and a remainder tree, and an induction on the number of leaves; the lower bound is imported from Theorem 7 of [15].

Significance. The result is a natural tight asymptotic in discrepancy theory for trees and confirms two conjectures from [15]. The random construction is elegant, the constant matches the star case, and the lower bound from [15] is correctly invoked. The paper does not include machine-checked proofs or code, but the probabilistic estimates are standard and the main ideas are sound. However, the proof as printed contains a false inequality in the main decomposition in §2, Eq. (7), and a local gap in Claim 2.3; both are repairable. The proof of the secondary theorem, Theorem 1.4, is only sketched and needs to be written out.

major comments (3)

[§2, Eq. (7)] The inequality ∑_{i=1}^r D_d(F_i) ≤ max_{a∈S^d} R_a ≤ φ(ℓ_F) is false in general. For example, take a path v_1...v_m and attach two leaves to each v_i; after the reduction in Claim 2.3, each F_i is a star with two leaves (or one leaf at the endpoints), and for each such small star D_d(F_i)=1. Hence the left-hand side equals Θ(m), while φ(ℓ_F) ∼ ℓ_F/(dB(d/2,1/2)) = (1+o(1))m/2 for d=2, and more generally the leading constant 1/(dB) is < 1. This makes the derivation of (8) invalid as printed. The intended argument can be repaired by proving directly that, with a single random coloring of all edges of F as in Lemma 2.1, the contribution of F to any subtree of T has norm at most φ(ℓ_F), yielding D_d(T) ≤ D_d(R)+φ(ℓ_F). The current (6)–(7) transition should be rewritten accordingly.
[§2, Claim 2.3] The proof of (5) does not cover subtrees \hat T that contain the edge xy but not yz. The only such connected subtree is {xy}, and the displayed equality would read f(xy)=0, which is generally false. The claim is still true because |f(xy)|=|f(yz)| and the imbalance of {xy} is realized by the subtree {yz} of T', but this exceptional case must be handled explicitly. Since Claim 2.3 is used repeatedly in the induction for Theorem 1.2, this is a load-bearing gap.
[§2, Claim 2.4 and proof of Theorem 1.4] The proof of Theorem 1.4 is only sketched. The construction of \hat T' from \hat T in Claim 2.4 is described in prose ('cutting terminal paths', 'similarly to the previous case') without a precise invariant that the two sums differ by at most one, and the case where the root r lies outside T' is not fully justified. The 'analogue of Lemma 2.1 for oriented discrepancy' is never stated or proved. Since Theorem 1.4 is one of the two main results, these arguments should be written out in full.

minor comments (4)

[§2, Claim 2.2] The phrase 'for x sampled uniformly at random in S^{d-1}' should read 'in S^d': the density computation that follows (with measure sin^{d-1}θ dθ) is for S^d, and the formula E[|⟨x,a⟩|] = 2/(d B(d/2,1/2)) is correct for x ∈ S^d.
[§2, proof of Theorem 1.4] The expression '⃗D(S_d)' should be '⃗D(S_ℓ)': S_d denotes the d-sphere, while the star with ℓ leaves is S_ℓ.
[§2, Lemma 2.1] The notation ⟨x_i · a⟩ is unusual; please use ⟨x_i, a⟩ consistently.
[§2, Eq. (4)] The first inequality in (4), D_d(S_ℓ) ≤ max_{ε_i ∈ {−1,1}} ‖∑ ε_i x_i‖, is true but merits a sentence: subtrees of the star correspond to 0/1 choices of elements of K, and any such choice is dominated in norm by some ±1 choice over the pairs.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the upper bound is derived internally and the lower bound is imported from an external theorem.

full rationale

Theorem 1.2's upper bound is self-contained: Lemma 2.1 independently computes the expectation E[|<x,a>|] = 2/(d B(d/2,1/2)) from the geometry of the sphere, then uses an epsilon-net and Chernoff bound to obtain D_d(S_l) ≤ cd*l + O(l^(3/4)). The reduction from general trees to stars is done via the decomposition T = F ∪ R and Claim 2.3, not by assuming the desired constant. The matching lower bound is imported from Theorem 7 of [15], an external paper by different authors, and the paper's own star computation independently reproduces the same constant, so the equality is not forced by a self-citation chain. The only self-citation, [14], appears in the introduction as background on dense-graph discrepancy and plays no role in the proof of Theorem 1.2 or Theorem 1.4. Consequently, no prediction is defined in terms of its target, no fitted parameter is renamed as a prediction, and no load-bearing step reduces to itself. The localized proof gaps noted in Claim 2.3 and Claim 2.4 are correctness concerns, not circularity. Honest non-finding is appropriate.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The upper bound is self-contained; the lower bound is the only external input. No fitting or invented entities.

assumptions (3)

domain assumption Lower bound D_d(T) ≥ ℓ/(d B(d/2,1/2)) from Theorem 7 of [15]
Imported from prior paper; the present paper proves only the matching upper bound.
standard math Existence of an ε-net on S^d of size O((1+2/ε)^{d+1})
Used in Lemma 2.1 to uniformly bound R_a; cited to Vershynin [17].
standard math Chernoff bound for sums of independent bounded random variables
Used in Claim 2.2 to show R_a concentrates around its mean.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A note on high-dimensional discrepancy of subtrees." pith.science (2026). https://pith.science/paper/IDXEGCI3

@misc{pith2026241204170,
  author       = {Pith},
  title        = {Pith review of: A note on high-dimensional discrepancy of subtrees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IDXEGCI3}},
  note         = {Machine review of arXiv:2412.04170}
}

abstract

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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 15 canonical work pages

[15]

Krishna, P

T. Krishna, P. Michaeli, M. Sarantis, F. Wang, and Y. Wan g. Discrepancies of subtrees. Graphs and Combinatorial Optimization: from Theory to Applicatio ns, pages 81–93, 2023

work page 2023
[1]

Balogh, B

J. Balogh, B. Csaba, Y. Jing, and A. Pluhár. On the discrep ancies of graphs. The Electronic Journal of Combinatorics , 27, 2020. 14 pp

work page 2020
[2]

Balogh, B

J. Balogh, B. Csaba, A. Pluhár, and A. Treglown. A discrep ancy version of the Hajnal– Szemerédi theorem. Combinatorics, Probability and Computing , 30(3):444–459, 2021

work page 2021
[3]

Beck and W

J. Beck and W. W. L. Chen. Irregularities of distribution . Cambridge Tracts in Mathematics. Cambridge University Press, 1987

work page 1987
[4]

D. Bradač. Powers of Hamilton cycles of high discrepancy are unavoidable. The Electronic Journal of Combinatorics , 29, 2022. 26 pp

work page 2022
[5]

Bradač, M

D. Bradač, M. Christoph, and L. Gishboliner. Minimum Deg ree Threshold for H-factors with High Discrepancy. arXiv preprint arXiv:2302.13780 , 2023

arXiv 2023
[6]

Chazelle

B. Chazelle. The Discrepancy Method: Randomness and Complexity . Cambridge University Press, USA, 2000

work page 2000
[7]

Erdős, Z

P. Erdős, Z. Füredi, M. Loebl, and V. T. Sós. Discrepancy o f trees. Studia Scientiarum Mathematicarum Hungarica, 30(1-2):47–57, 1995. 7

work page 1995

Show all 18 references

[8]

Erdös and J

P. Erdös and J. Spencer. Imbalances in k-colorations. Networks, 1(4):379–385, 1971

1971
[9]

Freschi, J

A. Freschi, J. Hyde, J. Lada, and A. Treglown. A note on col or-bias Hamilton cycles in dense graphs. SIAM Journal on Discrete Mathematics , 35(2):970–975, 2021

2021
[10]

Gishboliner, M

L. Gishboliner, M. Krivelevich, and P. Michaeli. Color -biased Hamilton cycles in random graphs. Random Structures & Algorithms , 60(3):289–307, 2022

2022
[11]

Gishboliner, M

L. Gishboliner, M. Krivelevich, and P. Michaeli. Discr epancies of spanning trees and Hamilton cycles. Journal of Combinatorial Theory, Series B , 154:262–291, 2022

2022
[12]

Gishboliner, S

L. Gishboliner, S. Glock, and A. Sgueglia. Tight Hamilt on cycles with high discrepancy. arXiv preprint arXiv:2312.09976, 2023

2023 arXiv
[13]

Hajnal and E

A. Hajnal and E. Szemerédi. Proof of a conjecture of P. Er dős. Colloq Math Soc János Bolyai , 4:601–623, 1970

1970
[14]

Hollom, L

L. Hollom, L. Lichev, A. Mond, and J. Portier. Discrepan cies of spanning trees in dense graphs. arXiv preprint arXiv:2410.17034 , 2024

2024 arXiv
[16]

Matoušek

J. Matoušek. Geometric discrepancy: An illustrated guide , volume 18. Springer Science & Business Media, 1999

1999
[17]

Vershynin

R. Vershynin. Introduction to the non-asymptotic anal ysis of random matrices. arXiv preprint arXiv:1011.3027, 2010

2010 arXiv
[18]

H. Weyl. Über die Gleichverteilung von Zahlen mod. Eins . Mathematische Annalen , 77(3): 313–352, 1916. 8

1916

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.

[1] [15]

Krishna, P

T. Krishna, P. Michaeli, M. Sarantis, F. Wang, and Y. Wan g. Discrepancies of subtrees. Graphs and Combinatorial Optimization: from Theory to Applicatio ns, pages 81–93, 2023

work page 2023

[2] [1]

Balogh, B

J. Balogh, B. Csaba, Y. Jing, and A. Pluhár. On the discrep ancies of graphs. The Electronic Journal of Combinatorics , 27, 2020. 14 pp

work page 2020

[3] [2]

Balogh, B

J. Balogh, B. Csaba, A. Pluhár, and A. Treglown. A discrep ancy version of the Hajnal– Szemerédi theorem. Combinatorics, Probability and Computing , 30(3):444–459, 2021

work page 2021

[4] [3]

Beck and W

J. Beck and W. W. L. Chen. Irregularities of distribution . Cambridge Tracts in Mathematics. Cambridge University Press, 1987

work page 1987

[5] [4]

D. Bradač. Powers of Hamilton cycles of high discrepancy are unavoidable. The Electronic Journal of Combinatorics , 29, 2022. 26 pp

work page 2022

[6] [5]

Bradač, M

D. Bradač, M. Christoph, and L. Gishboliner. Minimum Deg ree Threshold for H-factors with High Discrepancy. arXiv preprint arXiv:2302.13780 , 2023

arXiv 2023

[7] [6]

Chazelle

B. Chazelle. The Discrepancy Method: Randomness and Complexity . Cambridge University Press, USA, 2000

work page 2000

[8] [7]

Erdős, Z

P. Erdős, Z. Füredi, M. Loebl, and V. T. Sós. Discrepancy o f trees. Studia Scientiarum Mathematicarum Hungarica, 30(1-2):47–57, 1995. 7

work page 1995