It's well known that for any graph $G = (V,E)$ that if $G$ is not connected, then its compliment $\overline{G}$ is connected. So, it's impossible to have both $G$ and $\overline{G}$ be disconnected. However, it's entirely possible for both $G$ and $\overline{G}$ to be connected. Is anything known about the probability that a random graph has both $G$ and $\overline{G}$ connected? For simplicity say $G(n,1/2)$?
$\begingroup$
$\endgroup$
3
-
2$\begingroup$ 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. $\endgroup$– Brendan McKayCommented Apr 9, 2021 at 3:43
-
$\begingroup$ That's very useful, thank you. Do you have a reference in mind? $\endgroup$– MathManiac5772Commented Apr 9, 2021 at 3:46
-
2$\begingroup$ 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$)$. $\endgroup$– James MartinCommented Apr 9, 2021 at 10:58
Add a comment
|