Skip to main content
3 of 8
added 87 characters in body

Random graphs constructed by many linear size matchings

Let $G_{n,d}$ be $d$-regular random graph. We know that for $d \geq 3$, $G \in G_{n,d}$ a.a.s. has a $1$-factorisation when $n$ is even.

So, the resulting graph that obtained from randomly choosing $d$ disjoint perfect matchings a.a.s. is $G_{n,d}$.

Then if we randomly choosing $d$ disjoint matchings of size $kn$ (for some $k\in(0,\frac{1}{2})$), Is there a characterization of the resulting graph distribution?

Is it random graph obtained from random choosing from all graphs with $kd$ edges and $\Delta \leq d$?

In particular, for $k=\frac{1}{4}$, is the resulting graph $G_{n,\frac{d}{2}}$?