← All problems

Complex discrepancy conjecture for trees

3 years old · traced to

Let TT be a tree with ℓ\ell leaves, let T\mathcal{T} denote the family of trees used in the discrepancy definition, and let D1(T,T)\mathcal{D}^1(T,\mathcal{T}) denote the one-dimensional, or complex, discrepancy. Write Δ(T)\Delta(T) for the maximum degree of TT. Complex discrepancy conjecture. For every tree TT with ℓ\ell leaves,

D1(T,T)≥12sin⁡(π2ℓ)=(1+o(1))ℓπ.\mathcal{D}^1(T,\mathcal{T})\ge \frac{1}{2\sin\left(\frac{\pi}{2\ell}\right)}=\left(1+o(1)\right)\frac{\ell}{\pi}.

If, in addition, Δ(T)=ω(1)\Delta(T)=\omega(1), then

D1(T,T)=(1+o(1))ℓπ.\mathcal{D}^1(T,\mathcal{T})=\left(1+o(1)\right)\frac{\ell}{\pi}.

The preceding theorem proves the weaker universal lower bound D1(T,T)≥ℓ/π\mathcal{D}^1(T,\mathcal{T})\ge \ell/\pi; the conjecture proposes the sharp trigonometric bound and asymptotic equality for trees of unbounded maximum degree.

References
  1. Tarun Krishna, Peleg Michaeli, Michail Sarantis, Fenglin Wang and Yiqing Wang, “Discrepancies of subtrees”, arXiv:2302.08557 (2023).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.