Concentration conjecture for the path-covering number in random trees

Let TT be the random tree under consideration, let tt denote its size parameter, and let cov(T)\operatorname{cov}_\ell(T) be the minimum number of paths of length at most \ell needed to cover TT. Suppose that =(t)\ell=\ell(t) satisfies

=o(t)\ell=o(\sqrt{t})

as tt tends to infinity. Concentration conjecture. For every δ>0\delta>0,

cov(T)E[cov(T)]<δt\left|\operatorname{cov}_\ell(T)-\mathbb{E}[\operatorname{cov}_\ell(T)]\right|<\frac{\delta t}{\ell}

with high probability. The preceding argument establishes concentration in a more restricted range, while the conjecture proposes that the weaker condition =o(t)\ell=o(\sqrt{t}) suffices; it remains open in the supplied source.

Sources & referencesView supporting material

Primary source

Vesna Iršič, Julien Portier and Leo Versteegen, “Packing and finding paths in sparse random graphs”, arXiv:2409.02812 (2024).

Additional references

3 papers in this index state this conjecture (2015–2024). The statement above is taken from the most recent of them; the others are arXiv:2003.08456, arXiv:1502.04061.

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.