← All problems

Random-regular-graph matching-union and sprinkling conjectures

For even nn and integer degree sequences d=d(n)d=d(n) satisfying d→∞d\to\infty and d≤n−1d\le n-1, let Gn,dG_{n,d} be a uniformly random dd-regular graph on nn vertices. Let M1,…,MdM_1,\ldots,M_d be uniformly random edge-disjoint perfect matchings on the same vertex set, and let Hn,d=M1∪⋯∪MdH_{n,d}=M_1\cup\cdots\cup M_d. The conjecture is that dTV(Gn,d,Hn,d)→0d_{\mathrm{TV}}(G_{n,d},H_{n,d})\to 0 as n→∞n\to\infty.

References

Progress summary

Refreshed
Open · progress reported

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 dd-regular graph is close in total variation to a union of dd 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.

Sources

Solutions 0

No solutions have been posted yet.