I would like to answer the following basic question:

Let $V$ be a collection of $n$ vertices and fix $x$ and $y$ in $V$. Let $G$ be a random graph on $n$ vertices and $M$ edges. What is the probability that $x$ and $y$ belong to the same connected component?

I've tried doing this by hand and I can not get anywhere with it. It seems like such a basic question to ask that I'm sure its been done in the literature somewhere but I can not find it. My thoughts now lead towards random graph theory and asymptotic probabilities.

I'd be grateful for any help you can provide.

  • $\begingroup$ What exactly is random here? Is $G$ fixed and we choose $x,y$ uniformly at random? Or is $G$ also a random graph, for example $G \in \mathcal G(n,p)$, where $\mathcal G(n,p)$ is the class of Erdös-Renyi graphs? $\endgroup$ – Stefan Dec 7 '18 at 10:06
  • $\begingroup$ @Stefan, $G$ is random here and it belongs to the model $\mathcal{G}(n,M)$. I've edited the question so it should be more specific. $\endgroup$ – Chris Cave Dec 7 '18 at 10:18
  • 1
    $\begingroup$ @coffeemath, that is part of the question. Not only how many connected components there are but also how large they are. $\endgroup$ – Chris Cave Dec 7 '18 at 10:18
  • 3
    $\begingroup$ You can deduce the answer, in a form that's probably nearly as strong as possible, from known information about the giant component of random graphs. $\endgroup$ – Greg Martin Dec 7 '18 at 11:18
  • $\begingroup$ @ChrisCave Got it. Will delete my comment. $\endgroup$ – coffeemath Dec 7 '18 at 18:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.