Tight noise thresholds for root confidence sets in preferential and uniform attachment

Let $\bm{G}_n$ be a latent growth-process network with parameters $(\alpha,\beta,\theta)$, where $\alpha,\beta\in\{0,1\}$ specify the attachment mechanism and $\theta\in[0,1]$ is the noise level. Let $B_{\epsilon}(\bm{G}_n^*)$ denote the confidence set for the root, and call a confidence set asymptotically valid if it has the prescribed asymptotic coverage.

Noise-threshold conjecture. For linear preferential attachment (LPA), corresponding to $\alpha=0$ and $\beta=1$, if $\theta=o(n^{-1/2})$, then

$$|B_{\epsilon}(\bm{G}_n^*)|=O_p(1),$$

whereas if $\theta=\omega(n^{-1/2})$, every asymptotically valid confidence set has size diverging with $n$. For uniform attachment (UA), corresponding to $\alpha=1$ and $\beta=0$, if $\theta=o(\frac{\log n}{n})$, then

$$|B_{\epsilon}(\bm{G}_n^*)|=O_p(1),$$

whereas if $\theta=\omega(\frac{\log n}{n})$, every asymptotically valid confidence set has size diverging with $n$.

These rates are proposed as tight thresholds separating bounded root-confidence sets from unavoidable divergence. The surrounding results establish weaker guarantees for uniform attachment, and simulations suggest bounded confidence-set size below the stated threshold; the conjectured sharpness of both thresholds remains open.