4
$\begingroup$

In the context of Euclidean graphs with vertices randomly embedded in either a 2D plane (for instance square with length $L$) or in 3D (similarly, cube of side $L$), where an edge between two given vertices $u,v$ is placed if their euclidean distance $d(u,v)\le \epsilon,$ with $\epsilon$ be being a given threshold distance according to which the edges are assigned:

  • Are the connectivity properties of such euclidean graphs generally well-known? For example, questions pertaining to size of largest components, or the component size distribution, for given number of vertices and $\epsilon/L$ relation. Any related piece of literature would be highly useful.
  • A concrete question that I've been wondering about is: What is the probability distribution of size of connected components in the graph (size here as in number of vertices per component)? That is, do we know (or could it be trivially shown) the fraction of components $F(x)$ that contain $x$ vertices? Again assuming basic graph properties such as number of vertices $n$ and $\epsilon/L$ are given.

In case the 3d discussions may be too involved, let us assume a 2d case, so a graph embedded onto a L by L square, with number of vertices $n$ and the $\epsilon/L$ ratio given.

$\endgroup$
  • 2
    $\begingroup$ These graphs are well-studied under the name "random geometric graphs". I don't know offhand what's known about the distribution of component sizes. $\endgroup$ – Ben Barber Oct 17 '18 at 14:45
  • 1
    $\begingroup$ It became clear after posting an answer that a similar question has been asked previously here: mathoverflow.net/questions/76153/…. $\endgroup$ – Josiah Park Oct 18 '18 at 6:15
1
$\begingroup$

A geometric random graph $G(\mathbf{X}_{n},r)$ is given by a threshold distance, $r$, for which vertices, $X$ and $Y$ in the vertex set $\mathbf{X}$ with $\|X-Y\|\leq r$ are connected, and a point process $\mathbf{X}_{n}:=\bigcup\limits_{i=1}^n X_{i}$, where $X_{i}$ are random variables. According to M. Penrose there is a type of phase change in the asymptotic behavior of random geometric graphs with vertices in $C=[-\frac{1}{2},\frac{1}{2}]^d$ (and other graphs) when the scaling between the number of points and distances is varied. Namely there is what is called the "super-connective" regime, where $$\frac{nr_{n}^d}{\log n}\rightarrow \infty \text{ as } n\rightarrow \infty$$ and the "sub-connective" regime where $$ \frac{nr_{n}^d}{\log n}\rightarrow 0 \text{ as }n\rightarrow \infty.$$ Because of this, results on connectivity asymptotics are phrased for particular growth rates of $r_{n}$. Let $f(x)$ be the uniform density on $C=[-\frac{1}{2},\frac{1}{2}]^d$ with $F(A)=\int\limits_{A} f(x) dx$ its distribution function and let $B(x;r)$ be the ball of radius $r$ centered at $x$. Introduce the auxiliary function $$\psi_{n,r_{n}}(x)=n\ exp(-nF(B(x;r_{n}))).$$ Now, let $K_{n}$ be (the distribution for) the number of connected components of $G(\mathbf{X_{n}},r_{n})$. Then the following asymptotics hold (Theorem 13.11 in M. Penrose)

Theorem - Let $r_{n}$ be taken so that $$\lim\limits_{n\rightarrow\infty} nr_{n}^d =\infty \text{ and }\lim\limits_{n\rightarrow \infty} n\int\limits_{C} \psi_{n,r_{n}}(x) dx=\beta .$$ Then $K_{n}-1\rightarrow P(\beta)$ in distribution as $n\rightarrow \infty$ where $P$ is the Poisson distribution.

This result is in the last chapter of Penrose's book Random Geometric Graphs which you may find in answers for your questions.

$\endgroup$
  • $\begingroup$ Thank you very much, this is indeed along the lines I've been looking for. So if I understood correctly, the 1st part of your answer is saying that if the number of isolated vertices tends to 0 in the asynmptotic limit then the graph is connected. The 2nd part, suggests that the number of components in the same limit are Poisson distributed. I hope I've understood correctly so far. Do you reckon the said theorem tells us potentially anything about the distribution of component orders? (number of contained vertices) $\endgroup$ – user929304 Oct 18 '18 at 9:53
  • $\begingroup$ @user929304 There are some results on the asymptotics of the $j$th largest component of $G$, $L_{j}(G)$ in section 9.3 of Penrose. $\endgroup$ – Josiah Park Oct 18 '18 at 21:33
  • $\begingroup$ Thanks. Unfortunately at the moment i dont have access to the book and have been unable to find excerpts of it. $\endgroup$ – user929304 Oct 19 '18 at 19:42

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.