Concentration conjecture for the path-covering number in random trees

About 11 years old · traced to

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.

References

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.