Odd-vertex perfect matching conjecture in random graphs
Let be the binomial random graph. Its odd-degree vertices are the vertices for which is odd.
Odd-vertex matching conjecture. If
then asymptotically almost surely 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 , but only states the displayed range and leaves it as an open question.
References
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.