Prescribed-parity perfect matching conjecture in random graphs
Prescribed-parity perfect matching conjecture in random graphs
Let be the vertices of , and let satisfy
The prescribed parity class is the set of vertices whose degrees satisfy the congruences specified by .
Prescribed-parity matching conjecture. If , then asymptotically almost surely contains a perfect matching on
This is a stronger statement than the odd-degree matching conjecture and is motivated by the need to realize the optimal leave in a final random slice. The source presents 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.