PreprintarXiv licencearXiv
Optimal path decompositions of sparse random graphs
Abstract
Let odd(G) be the number of odd-degree vertices of a graph G. We prove that, if p=o(1) and np/log n→∞, then with probability tending to one the random graph G(n,p) has an edge decomposition into exactly odd(G)/2 paths. This confirms a conjecture of Glock, Kühn and Osthus from 2016. The proof combines a key lemma with cycle decompositions of random graphs.
Related
- Path Decompositions of Sparse Graphs via Gaussian Sweeps and Faster Exponential Algorithms
- Coloring sparse random Cayley graphs
- A first order phase transition for lower tails in sparse random graphs
- The lower tail of triangle counts in sparse random graphs
- Local Convergence of Triadic Closures of Sparse Random Graphs
BibTeX
@misc{lin2026optimal,
title = {{Optimal path decompositions of sparse random graphs}},
author = {Jifu Lin and Heng Yang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.37173},
eprint = {2610.37173},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.37173},
}
RIS
TY - UNPB
TI - Optimal path decompositions of sparse random graphs
AU - Jifu Lin
AU - Heng Yang
PY - 2026
DA - 2026/10/27
PB - arXiv
DO - 10.48550/arxiv.2610.37173
UR - https://arxiv.org/abs/2610.37173
AB - Let odd(G) be the number of odd-degree vertices of a graph G. We prove that, if p=o(1) and np/log n→∞, then with probability tending to one the random graph G(n,p) has an edge decomposition into exactly odd(G)/2 paths. This confirms a conjecture of Glock, Kühn and Osthus from 2016. The proof combines a key lemma with cycle decompositions of random graphs.
ER -