Contiguity conjecture for unions of random perfect matchings
Contiguity conjecture for unions of random perfect matchings
Let be even and let . For each even , fix a set of -regular graphs on vertices. Let denote the disjoint union of random perfect matchings.
Random matching decomposition conjecture. The event that the disjoint union belongs to holds with high probability if and only if the event that a uniform random -regular graph belongs to holds with high probability:
The paper proves one implication for and states that, more generally, both the implication and its converse are believed to hold throughout .
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
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.