Prescribed-parity perfect matching conjecture in random graphs

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 pn1/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.

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.