Concentration conjecture for the path-covering number in random trees
Concentration conjecture for the path-covering number in random trees
Let be the random tree under consideration, let denote its size parameter, and let be the minimum number of paths of length at most needed to cover . Suppose that satisfies
as tends to infinity. Concentration conjecture. For every ,
with high probability. The preceding argument establishes concentration in a more restricted range, while the conjecture proposes that the weaker condition 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.