Extremal Difficulty of Tree Flow Estimation

Definitions and mathematical statement

For an integer $n\geq 2$, the path $P_n$ is the graph with vertex set $\{1,\ldots,n\}$ and edges $\{i,i+1\}$ for $1\leq i<n$. The star $S_n$ is the graph on the same vertex set with edges $\{1,i\}$ for $2\leq i\leq n$. These definitions specify only the underlying graph shapes; they do not specify roots, edge directions, or a statistical model.

Source question. For least-squares estimation of noisy tree flows, is the path the hardest flow-estimation problem and the star the easiest?

A conditional mathematical schema for this question is the following. If comparison is intended among trees with the same number $n$ of vertices, let $\mathcal T_n$ denote the intended class of admissible trees, including any required rooting or orientation, and let $D(T)$ denote the intended numerical measure of difficulty for least-squares flow estimation on $T$, with larger values meaning greater difficulty. The proposed extremal comparison would then be \[ D(S_n)\leq D(T)\leq D(P_n) \qquad\text{for every }T\in\mathcal T_n, \] for each admissible $n$, with $P_n$ and $S_n$ equipped with the required additional structure. This is a formulation schema only: the supplied record does not specify equal-size comparison, the admissible sizes, the class $\mathcal T_n$, or the functional $D$.

In particular, the source does not define a tree flow, its feasibility constraints or parameter bounds, the observation locations, the noise distribution or scale, the least-squares criterion, or the loss and risk used to compare difficulty. It also does not specify whether the comparison is pointwise, worst-case, asymptotic, or up to constants. Consequently, the supplied question does not determine a unique quantified statistical proposition without further source information.

Short English statement

The question asks whether paths make least-squares estimation of noisy tree flows hardest and stars make it easiest. A precise extremal comparison requires the flow model, noise assumptions, comparison class, and measure of estimation difficulty, which the supplied record does not provide. The supplied status is partially_solved; this draft does not independently verify that assessment.

Sources

• Local UnsolvedMath registry record, permanent ID $30003092$, title Extremal Difficulty of Tree Flow Estimation, source problem code catalogue entry; supplied as part of the Oberwolfach Reports Open Problems collection. The record lists the proposed year as 2016 and supplies no individual proposer. Its exact statement label and byte-for-byte retention note are supplied registry metadata, not independent source verification.
• Supplied report citation: Computationally and Efficient Inference for Complex Large-scale Data (2016), Oberwolfach Reports, pp. 741--796, DOI 10.4171/owr/2016/16. https://doi.org/10.4171/owr/2016/16. The supplied background describes Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions; no problem-specific page is supplied.
• Supplied literature reference: Chatterjee--Lafferty, DOI 10.1109/TIT.2017.2782369. https://doi.org/10.1109/TIT.2017.2782369. No article title or fuller bibliographic information is supplied.
• Literature assessment dated exactly 2026-08-21: supplied dated curation, not independently verified. The supplied status is partially solved. The assessment reports rigorous bounds for path-like and logarithmic-depth regimes, analysis of interpolating trees, and evidence that paths and stars are not extremal; it also reports a remaining minimax gap and no complete ordering of tree difficulties. The background calls this a dated literature triage derived from the supplied OWR curation and requests independent verification of time-sensitive status and cited claims. Neither linked source has been consulted for this draft.