1
$\begingroup$

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?

Improve this question
$\endgroup$
19
  • $\begingroup$ What do you do with multiple edges which appear in the union of independent matchings? $\endgroup$
    – Fedor Petrov
    Commented Jun 5, 2023 at 11:57
  • $\begingroup$ @FedorPetrov We randomly choose disjoint matchings. So there doesn't exist multiple edges. $\endgroup$
    – Yuhang Bai
    Commented Jun 5, 2023 at 13:14
  • $\begingroup$ So, we consider all sets of $d$ disjoint matchings with equal probability, right? But then how can it be $G_{n,d/2}$, if the degrees may be as large as $d$? $\endgroup$
    – Fedor Petrov
    Commented Jun 5, 2023 at 14:20
  • $\begingroup$ We can understand it as uniform randomly choosing $d$ disjoint matching from $K_n$. I guess this may be a regular graph in the asymptotic sense（a.a.s.）. $\endgroup$
    – Yuhang Bai
    Commented Jun 5, 2023 at 14:30
  • 1
    $\begingroup$ The symmetry argument here is not correct. Random regular graphs formed by sampling all regular graphs with equal probability do not have the same asymptotic distribution as random regular graphs made by uniformly choosing disjoint perfect matchings. For example, the expected number of short cycles is different. The reason is that a graph with a large number of 1-factorizations is more likely to be generated than one with a small number of 1-factorizations. However, for constant $d\geq 3$ it has been proved that the distributions are "contiguous". Look for work of N. C. Wormald. $\endgroup$
    – Brendan McKay
    Commented Jun 17, 2023 at 13:51

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .