Contiguity conjecture for unions of random perfect matchings

Let nn be even and let d[3,n3]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 probabilityG(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 dn1/10d\le n^{1/10} and states that, more generally, both the implication and its converse are believed to hold throughout d[3,n3]d\in[3,n-3].

Sources & referencesView supporting material

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.