Odd-vertex perfect matching conjecture in random graphs
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.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.