Timeline for Random graphs constructed by many large matchings
Current License: CC BY-SA 4.0
27 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 18, 2023 at 1:42 | history | edited | Yuhang Bai | CC BY-SA 4.0 |
added 9 characters in body
|
| Jun 17, 2023 at 14:02 | comment | added | Yuhang Bai | Thank you! I got it. | |
| Jun 17, 2023 at 13:51 | comment | added | Brendan McKay | 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. | |
| Jun 17, 2023 at 1:40 | history | edited | Yuhang Bai | CC BY-SA 4.0 |
added 8 characters in body
|
| Jun 6, 2023 at 11:53 | comment | added | Yuhang Bai | Let us continue this discussion in chat. | |
| Jun 6, 2023 at 8:50 | comment | added | Yuhang Bai | Yes, you are right. By symmetry, we can get it. | |
| Jun 6, 2023 at 8:45 | comment | added | Fedor Petrov | We need "every graph is chosen with equal probability", right? Not just "every edge". | |
| Jun 6, 2023 at 8:42 | comment | added | Yuhang Bai | For $G_{n,d}$, we randomly choose a graph from all $d$-regular graph. For our random process, we also randomly choose a graph from all $d$-regular graph (a.a.s.), because every edge is is chosen with equal probability, it is symmetrical. | |
| Jun 6, 2023 at 7:55 | comment | added | Fedor Petrov | It is not so simple. If two distributions have the same support, they are not necessarily the same. | |
| Jun 6, 2023 at 7:40 | comment | added | Yuhang Bai | For example, the resulting graph that obtained from randomly choosing $d$ disjoint perfect matchings a.a.s. is $G_{n,d}$. We denote the resulting graph by $G$. First, it is easy to see that $G$ is a $d$-regular graph. Second, $G_{n,d}$ a.a.s. has a 1-factorisation when $n$ is even. So the set of graphs that can be obtained from randomly choosing $d$ disjoint perfect matchings a.a.s. are same as the set of all regular graph.Therefore, the resulting graph distribution is $G_{n,d}$. | |
| Jun 6, 2023 at 7:22 | comment | added | Fedor Petrov | Yes, but $G_{n,d}$ is not a collection of graphs, it is a distribution on graphs. | |
| Jun 6, 2023 at 6:54 | comment | added | Yuhang Bai | The property $Q$ is an intuitive statement, formally, you can also think of it as a collection of graphs. This is also why we say that $P(G\in Q)$. I think "being a random regular graph" is correct. | |
| Jun 6, 2023 at 6:48 | comment | added | Fedor Petrov | Well, but "being a random regular graph" is not a deterministic property. | |
| Jun 6, 2023 at 6:47 | comment | added | Yuhang Bai | Yes. It is a definition. | |
| Jun 6, 2023 at 5:13 | comment | added | Fedor Petrov | Ok, but it is about determinidtic property $Q$, right? | |
| Jun 6, 2023 at 2:39 | history | edited | Yuhang Bai | CC BY-SA 4.0 |
added 11 characters in body
|
| Jun 6, 2023 at 2:04 | history | edited | Yuhang Bai | CC BY-SA 4.0 |
added 52 characters in body
|
| Jun 6, 2023 at 1:55 | comment | added | Yuhang Bai | For a graph $G$ and a property $Q$, If $P(G \in Q) \rightarrow 1$, as $n \rightarrow \infty$, then we say that a graph $G$ a.a.s. satisfies the property $Q$. | |
| Jun 5, 2023 at 17:58 | comment | added | Fedor Petrov | I do not understand what exactly does it mean that two distributions on graphs coincide a.a.s, would you please elaborate? | |
| Jun 5, 2023 at 14:30 | comment | added | Yuhang Bai | 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.）. | |
| Jun 5, 2023 at 14:27 | history | edited | Yuhang Bai | CC BY-SA 4.0 |
added 7 characters in body
|
| Jun 5, 2023 at 14:20 | comment | added | Fedor Petrov | 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$? | |
| Jun 5, 2023 at 13:14 | comment | added | Yuhang Bai | @FedorPetrov We randomly choose disjoint matchings. So there doesn't exist multiple edges. | |
| Jun 5, 2023 at 11:57 | comment | added | Fedor Petrov | What do you do with multiple edges which appear in the union of independent matchings? | |
| Jun 5, 2023 at 7:19 | history | edited | Yuhang Bai | CC BY-SA 4.0 |
added 87 characters in body
|
| Jun 2, 2023 at 9:24 | history | edited | Yuhang Bai | CC BY-SA 4.0 |
added 4 characters in body
|
| Jun 1, 2023 at 12:03 | history | asked | Yuhang Bai | CC BY-SA 4.0 |