Timeline for Probability that a graph and its complement are connected
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 9, 2021 at 10:58 | comment | added | James Martin | If you know $P(G$ disconnected$)$ and you know $P(\overline{G}$ disconnected$)$, then because the events are disjoint (as you observed), you also know the probability of the union. So unless there is something special going on in your model which makes the union of those two events easier to study than the individual events themselves, your question just reduces to asking about the probability that a graph is connected. In the specific case $G(n, 1/2)$ it's particularly simple by symmetry: $P(G$ disconnected or $\overline{G}$ disconnected$)$ = $2P(G$ disconnected$)$. | |
| Apr 9, 2021 at 7:18 | history | edited | YCor | CC BY-SA 4.0 |
fixed typo
|
| Apr 9, 2021 at 3:46 | comment | added | MathManiac5772 | That's very useful, thank you. Do you have a reference in mind? | |
| Apr 9, 2021 at 3:43 | comment | added | Brendan McKay | Yes, the probability of both being connected is about $1-n 2^{-n+2}$ which is perilously close to 1. Any book on random graphs will have this type of information. | |
| Apr 9, 2021 at 3:16 | review | First posts | |||
| Apr 9, 2021 at 4:26 | |||||
| Apr 9, 2021 at 3:06 | history | asked | MathManiac5772 | CC BY-SA 4.0 |