Asymptotic oriented discrepancy conjecture for directed rooted trees

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.

Sources & referencesView supporting material

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.