Skip to main content
MathOverflow

Return to Question

Notice removed Draw attention by CommunityBot
Bounty Ended with no winning answer by CommunityBot
Notice added Draw attention by user929304
Bounty Started worth 50 reputation by user929304
tag edit
Link
Ben Barber
Ben Barber
  • 4.6k
  • 2
  • 25
  • 38
Random embedding added, unclear before
Source Link
user929304
user929304
  • 649
  • 6
  • 12

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.

In the context of Euclidean graphs 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.

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.

Source Link
user929304
user929304
  • 649
  • 6
  • 12

Component properties in Euclidean graphs with distance threshold

In the context of Euclidean graphs 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.