Odd-vertex perfect matching conjecture in random graphs

Let G(n,p)G(n,p) be the binomial random graph. Its odd-degree vertices are the vertices vv for which dG(n,p)(v)d_{G(n,p)}(v) is odd.

Odd-vertex matching conjecture. If

pn1/2,p\geq n^{-1/2},

then asymptotically almost surely G(n,p)G(n,p) contains a perfect matching on its odd-degree vertices.

This would attain the degree-parity contribution to the optimal triangle-packing leave. The source notes that the claim may hold already for pn1lognp\gg n^{-1}\log n, but only states the displayed range and leaves it as an open question.

Sources & referencesView supporting material

Primary source

Michelle Delcourt, Tom Kelly and Luke Postle, “Clique Decompositions in Random Graphs via Refined Absorption”, arXiv:2402.17857 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.