Skip to main content
added 9 characters in body
Source Link

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 contiguous with $G_{n,d}$.

If we randomly choosing $d$ disjoint matchings of size $(\frac{1}{2}-o(1))n$ , Is there a characterization of the resulting graph distribution?

In particularly, for fixed vertex $v$, we have $Pr(deg(v)=0)\leq o(1)$. Then a.a.s. $deg(v)=d$. And for a vertex set that has constant size, we have all vertex in this set have degree $d$. Furthermore, does resulting graph a.a.s. have a large induced subgraph with large minimum degree?

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}$.

If we randomly choosing $d$ disjoint matchings of size $(\frac{1}{2}-o(1))n$ , Is there a characterization of the resulting graph distribution?

In particularly, for fixed vertex $v$, we have $Pr(deg(v)=0)\leq o(1)$. Then a.a.s. $deg(v)=d$. And for a vertex set that has constant size, we have all vertex in this set have degree $d$. Furthermore, does resulting graph a.a.s. have a large induced subgraph with large minimum degree?

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 is contiguous with $G_{n,d}$.

If we randomly choosing $d$ disjoint matchings of size $(\frac{1}{2}-o(1))n$ , Is there a characterization of the resulting graph distribution?

In particularly, for fixed vertex $v$, we have $Pr(deg(v)=0)\leq o(1)$. Then a.a.s. $deg(v)=d$. And for a vertex set that has constant size, we have all vertex in this set have degree $d$. Furthermore, does resulting graph a.a.s. have a large induced subgraph with large minimum degree?

added 8 characters in body
Source Link

Random graphs constructed by many linear sizelarge 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 For a real number $\varepsilon(0<\varepsilon<\frac{1}{2})$, ifIf we randomly choosing $d$ disjoint matchings of size $(\frac{1}{2}-\varepsilon)n$$(\frac{1}{2}-o(1))n$ , Is there a characterization of the resulting graph distribution?

Is it random graph obtained from random choosing from all graphs withIn particularly, for fixed vertex $kd$ edges and$v$, we have $\Delta \leq d$$Pr(deg(v)=0)\leq o(1)$. Then a.a.s. $deg(v)=d$. And for a vertex set that has constant size, we have all vertex in this set have degree $d$. Furthermore, does resulting graph a.a.s. have a large induced subgraph with large minimum degree?

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

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 For a real number $\varepsilon(0<\varepsilon<\frac{1}{2})$, if we randomly choosing $d$ disjoint matchings of size $(\frac{1}{2}-\varepsilon)n$ , 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 $\varepsilon =\frac{1}{4}$, is the resulting graph a.a.s. $G_{n,\frac{d}{2}}$?

Random graphs constructed by many large 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}$.

If we randomly choosing $d$ disjoint matchings of size $(\frac{1}{2}-o(1))n$ , Is there a characterization of the resulting graph distribution?

In particularly, for fixed vertex $v$, we have $Pr(deg(v)=0)\leq o(1)$. Then a.a.s. $deg(v)=d$. And for a vertex set that has constant size, we have all vertex in this set have degree $d$. Furthermore, does resulting graph a.a.s. have a large induced subgraph with large minimum degree?

added 11 characters in body
Source Link

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 For a real number $\varepsilon(0<\varepsilon<\frac{1}{2})$, if we randomly choosing $d$ disjoint matchings of size $(\frac{1}{2}-\varepsilon)n$ , 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}$$\varepsilon =\frac{1}{4}$, is the resulting graph a.a.s. $G_{n,\frac{d}{2}}$?

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 For a real number $\varepsilon(0<\varepsilon<\frac{1}{2})$, if we randomly choosing $d$ disjoint matchings of size $(\frac{1}{2}-\varepsilon)n$ , 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 a.a.s. $G_{n,\frac{d}{2}}$?

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 For a real number $\varepsilon(0<\varepsilon<\frac{1}{2})$, if we randomly choosing $d$ disjoint matchings of size $(\frac{1}{2}-\varepsilon)n$ , 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 $\varepsilon =\frac{1}{4}$, is the resulting graph a.a.s. $G_{n,\frac{d}{2}}$?

added 52 characters in body
Source Link
Loading
added 7 characters in body
Source Link
Loading
added 87 characters in body
Source Link
Loading
added 4 characters in body
Source Link
Loading
Source Link
Loading