The large-error lower-bound conjecture for uniform attachment seed detection

Let $K(k,\ell,\varepsilon)$ denote the minimum number of vertices needed to identify a set containing the whole seed of a uniform attachment tree with probability at least $1-\varepsilon$, when the seed has $k$ vertices and $\ell$ leaves. There are universal constants $c_1,c_2,\varepsilon_0>0$ such that, whenever $k,\ell>c_1$,

$$K(k,\ell,\varepsilon_0)\ge c_2 k\ell.$$

Large-error lower-bound conjecture. The required confidence-set size is at least a constant multiple of $k\ell$ for sufficiently large seeds and a fixed positive error level. This conjectures a matching-order lower bound to the known upper bound in the regime where the error is bounded away from zero; the source presents it as an expression of the belief that the strategy based on likely vertices is close to optimal.