Glock–Kühn–Osthus path-decomposition conjecture
Let satisfy and . If , then with probability tending to as , the edge set can be partitioned into exactly paths, where denotes the number of vertices of odd degree in .
References
- Optimal path decompositions of sparse random graphs — arXiv — Jifu Lin, Heng Yang
Source: arXiv
Progress summary
The sparse random-graph conjecture remains open in the verified record, although exact formulas are known for dense random graphs.
Glock, Kühn, and Osthus formulated the conjecture in 2016: in the sparse regime and , a typical random graph should decompose into exactly paths. The available foundational sources label this statement a conjecture, not a theorem.
Known results
- For dense random graphs with constant , the minimum number of paths is (Glock, Kühn, Osthus, 2016).
- The linear-forest analogue extends into a sparse range, including , but this does not establish the exact path-decomposition conjecture.
- An approximate sparse path result follows by splitting cycles, while the exact statement remained open in the cited sources.
Current status (as of October 2026): Dense-graph and related linear-forest results are established, but the exact sparse path-decomposition conjecture remains open in the verified record.
Solutions 0
No solutions have been posted yet.