Norin–Turcotte exact random-cover conjecture

Let $T$ be a finite metric tree of total length $L$ , and let $r>0$ satisfy $L\ge 2r$ . Then there exists a probability distribution on $0$ -good ball covers of $T$ , with all ball radii in $[0,r]$ , such that the expected radius measure of the random cover is dominated by $\frac{L}{r}U[0,r]$ , where $U[0,r]$ denotes the uniform probability measure on $[0,r]$ . Equivalently, if $\mu_{\mathcal C}$ is the radius measure of a random cover $\mathcal C$ , then $\mathbb E[\mu_{\mathcal C}]\le \frac{L}{r}U[0,r]$ as measures on $[0,r]$ .

Equivalent formulations 1

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

Duality criterion for the exact radius budget
For a finite metric tree $T$ of length $L$ , a finite positive Borel measure $\beta$ on $[0,R]$ dominates the expected radius measure of a random $0$ -good ball cover if and only if $\sigma(T)\le \int_{[0,R]}\max_{v\in T}\sigma(B_T(v,s))\,d\beta(s)$ for every finite positive Borel measure $\sigma$ on $T$ ; it is enough to test finite atomic measures. Taking $R=r$ and $\beta=\frac{L}{r}U[0,r]$ gives a dual formulation of the conjecture.
source: Wu, Qi, Lu, Yong, “Exact random covers of metric trees: balanced rounding, duality, and sharp thresholds”

Sources & referencesView supporting material

Primary source

arXiv

Additional references

Exact random covers of metric trees: balanced rounding, duality, and sharp thresholds — arXiv

1 day ago

Progress summary

Refreshed 1 day ago

Claimed solved

The original authors left this sharp covering question open, but an August 2026 preprint now claims a full proof that has not yet been independently verified.

Norin and Turcotte stated the exact random-cover conjecture as Conjecture 6.1 in their 2022 paper: for metric trees satisfying $|T|\geq 2r$ , a probability distribution on covers should attain the sharp expected budget.

Known results

Norin and Turcotte (2022; published 2024) proved the asymptotic Burning Number Conjecture, $b(G)\leq (1+o(1))\sqrt{n}$ .
Norin and Turcotte (2022) established the exact random-cover statement for metric trees with at most three leaves.
They identified the regime $|T|<2r$ as an obstruction to the unrestricted formulation.

August 2026 claimed proof

An August 19, 2026 arXiv preprint claims the full conjecture, using fractional covers, compact rounding, balanced-matrix integrality, and duality; it also claims additional uniform radius regimes. This is an unrefereed claim, with no independent verification found.

Current status (as of August 2026): The conjecture has a claimed full proof in an unrefereed preprint, but remains unverified; the earlier published results cover only the asymptotic theorem and special tree classes.

Sources

No solutions have been posted yet.

Equivalent formulations 1

Duality criterion for the exact radius budget

Primary source

Additional references

Progress summary