Random-regular-graph matching-union and sprinkling conjectures
For even and integer degree sequences satisfying and , let be a uniformly random -regular graph on vertices. Let be uniformly random edge-disjoint perfect matchings on the same vertex set, and let . The conjecture is that as .
References
- Sprinkling for random regular graphs and Kim-Vu's sandwich conjecture — arXiv — Julien Portier
Source: arXiv
Progress summary
A new preprint establishes the conjectured random-matching construction only in a sparse range, so the full conjecture remains open.
The conjectures assert that random regular graphs can be represented or approximated by unions of independent edge-disjoint random regular graphs, including perfect-matchings sprinkling. The full assertions remain broader than the parameter ranges currently proved.
Known results
- Partial confirmations cover a perfect matching plus a sparse random regular graph, sufficiently sparse or dense degrees, and several broad-degree regimes.
- A 2025 preprint proves monotone couplings and union equivalence when both component degrees are sufficiently large, plus total-variation estimates for adding a matching in a limited range.
October 2026 sprinkling development
Julien Portier's preprint Sprinkling for random regular graphs and Kim–Vu's sandwich conjecture claims that, in a stated sparse regime, a uniform random -regular graph is close in total variation to a union of random edge-disjoint perfect matchings. This supplies a rigorous sprinkling representation and consequences for related sparse-graph conjectures, but does not settle the full problem.
Current status (as of October 2026): Partial parameter-range results are available, including the new claimed sparse-regime total-variation coupling, while the full matching-union and sprinkling conjectures remain open.
Solutions 0
No solutions have been posted yet.