Asymptotic oriented discrepancy conjecture for directed rooted trees

About 3 years old · traced to

Let TT be a tree with ℓ\ell leaves, and let DT\mathcal{DT} be the set of all directed rooted trees, namely trees with a distinguished root and all edges oriented away from it. Write D⃗(T,DT)\vec{\mathcal{D}}(T,\mathcal{DT}) for the oriented discrepancy of this family in TT. Asymptotic oriented discrepancy conjecture. For every such tree,

D⃗(T,DT)=(1+o(1))ℓ2.\vec{\mathcal{D}}(T,\mathcal{DT})=\left(1+o(1)\right)\frac{\ell}{2}.

The proven lower bound is ⌈ℓ/2⌉+1\lceil\ell/2\rceil+1, while the current general upper bound is ℓ\ell; the conjecture asks for an asymptotically matching upper bound.

References

Primary source

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.