← All problems

Glock–Kühn–Osthus path-decomposition conjecture

Let p=p(n)p=p(n) satisfy p=o(1)p=o(1) and np/log⁡n→∞np/\log n\to\infty. If G∼G(n,p)G\sim G(n,p), then with probability tending to 11 as n→∞n\to\infty, the edge set E(G)E(G) can be partitioned into exactly odd⁡(G)/2\operatorname{odd}(G)/2 paths, where odd⁡(G)\operatorname{odd}(G) denotes the number of vertices of odd degree in GG.

References

Source: arXiv

Progress summary

Refreshed
Open

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 p=o(1)p=o(1) and np/log⁡n→∞np/\log n\to\infty, a typical random graph should decompose into exactly odd⁡(G)/2\operatorname{odd}(G)/2 paths. The available foundational sources label this statement a conjecture, not a theorem.

Known results

  • For dense random graphs with constant pp, the minimum number of paths is max⁡{odd⁡(G)/2,⌈Δ(G)/2⌉}\max\{\operatorname{odd}(G)/2,\lceil\Delta(G)/2\rceil\} (Glock, Kühn, Osthus, 2016).
  • The linear-forest analogue extends into a sparse range, including log⁡117n/n≤p=o(1)\log^{117}n/n\le p=o(1), 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.

Sources

Solutions 0

No solutions have been posted yet.