1
$\begingroup$

Let $G = (V, E)$ be a graph on n vertices constructed in the following way:

Each vertex $v \in V$ is positioned uniform randomly in $[0, 1] × [0, 1]$.

Connect two vertices $u, v \in V$ if $d(v,u) ≤ r$ where $d$ is the Euclidean distance on a Torus.

I would like to prove that for $r = 3\cdot\sqrt{\frac{2log(n)}{n}}$ the graph is connected with probability at least $1-\frac{1}{log(n)}$

I'm not even sure how to formulate the probability $Pr[\text{graph is connected}]$. If I knew this I would probably be able to apply a union bound and go with an Azuma/Janson or similar bound.

Improve this question
$\endgroup$
7
  • $\begingroup$ What makes you think that for that specific value of $r$ that the graph is connected if you can't formalize what it means for the graph to be connected? $\endgroup$
    – Anthony Quas
    Commented Oct 30, 2014 at 19:02
  • 2
    $\begingroup$ @AnthonyQuas It seems as though the OP is saying that it is unclear how to express the probability that the graph is connected, not that there is any confusion regarding the definition of connectivity. $\endgroup$
    – Vidit Nanda
    Commented Oct 30, 2014 at 19:23
  • $\begingroup$ @AnthonyQuas Just like Vidit Nanda wrote, I know what it means for a graph to be connected. It's expressing the probability for this event that is my problem. Would you please consider taking back the down-vote? (if that was you). $\endgroup$
    – murv
    Commented Oct 30, 2014 at 19:35
  • $\begingroup$ Connectedness implies there is a spanning tree containing all vertices. Maybe you can use that? $\endgroup$
    – Per Alexandersson
    Commented Oct 30, 2014 at 20:12
  • 1
    $\begingroup$ Some very closely related questions are addressed in Balister, Bollobás and Sarkar: Percolation, connectivity, coverage and colouring of random geometric graphs, in the Handbook of large-scale random networks published by Springer. $\endgroup$
    – Anthony Quas
    Commented Oct 30, 2014 at 21:01

1 Answer 1

Reset to default
2
$\begingroup$

I don't remember the exact details, but the analysis of such problems can be found in Random Geometric Graphs by M. Penrose. http://www.bioinfo.org.cn/~wangchao/maa/Random_Geometric_Graphs.pdf

From what I remember, the key insight is that in the large n limit, connectivity occurs at the same threshold that isolated points disappear, which is straightforward to check for your problem using a union bound. The only remaining issue is the convergence rate, i.e. is 1/log(n) correct, which might require some effort.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .