Contiguity conjecture for unions of random perfect matchings

About 1 year old · traced to

Let nn be even and let d∈[3,n−3]d\in[3,n-3]. For each even nn, fix a set AnA_n of dd-regular graphs on nn vertices. Let G(n,1)⊕⋯⊕G(n,1)G(n,1)\oplus\dotsb\oplus G(n,1) denote the disjoint union of dd random perfect matchings.

Random matching decomposition conjecture. The event that the disjoint union belongs to AnA_n holds with high probability if and only if the event that a uniform random dd-regular graph belongs to AnA_n holds with high probability:

G(n,1)⊕⋯⊕G(n,1)∈An with high probability⟺G(n,d)∈An with high probability.G(n,1)\oplus\dotsb\oplus G(n,1)\in A_n\text{ with high probability}\quad\Longleftrightarrow\quad G(n,d)\in A_n\text{ with high probability}.

The paper proves one implication for d≤n1/10d\le n^{1/10} and states that, more generally, both the implication and its converse are believed to hold throughout d∈[3,n−3]d\in[3,n-3].

References

Primary source

Lawrence Hollom, Lyuben Lichev, Adva Mond, Julien Portier and Yiting Wang, “Monotonicity and decompositions of random regular graphs”, arXiv:2505.22875 (2025).

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.