Prescribed-parity perfect matching conjecture in random graphs

About 2 years old · traced to

Let v1,…,vnv_1,\ldots,v_n be the vertices of G(n,p)G(n,p), and let ϕ:[n]→{0,1}\phi:[n]\to\{0,1\} satisfy

∣{i∈[n]:ϕ(i)=1}∣ is even.\left|\{i\in[n]:\phi(i)=1\}\right|\text{ is even}.

The prescribed parity class is the set of vertices whose degrees satisfy the congruences specified by ϕ\phi.

Prescribed-parity matching conjecture. If p≥n−1/2p\geq n^{-1/2}, then asymptotically almost surely G(n,p)G(n,p) contains a perfect matching on

{vi:dG(n,p)(vi)≡ϕ(i)−1(mod2)}.\left\{v_i:d_{G(n,p)}(v_i)\equiv \phi(i)-1\pmod 2\right\}.

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.

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.