Paperlane

no. 7 · Tuesday 3 November 2026

Optimal path decompositions of sparse random graphs

Jifu Lin and Heng Yang

math.CO · v2 · 15 pp

Abstract

Let $\operatorname{odd}(G)$ be the number of odd-degree vertices of a graph $G$. We prove that, if $p=o(1)$ and $np/\log n\to\infty$, then with probability tending to one the random graph $G(n,p)$ has an edge decomposition into exactly $\operatorname{odd}(G)/2$ paths. This confirms a conjecture of Glock, Kühn and Osthus from 2016. The proof combines a local pairing argument based on the lopsided Lovász local lemma with cycle decompositions of random graphs.

comments
15 pages
fields
Combinatorics
pdf ↗ page arXiv:2610.37173 ↗