17
$\begingroup$

Let $S$ be a sphere of unit radius. Let $C_n$ be a collection of unit-radius circles/rings whose centers are (uniformly distributed) random points in $S$, and which are oriented (tilted) randomly (again, uniformly).

Q1. As $n \to \infty$, does the probability that all the rings in $C_n$ are linked together in one component approach $1$?

By "linked together" I mean that if you pick up any one ring, all the others are physically connected and would follow. For example, below there are $n=5$ rings, four of which are connected, but one (topmost) is not:
           RandCircleLinks

Q2. Same as Q1, but with $S$ a sphere of some (perhaps large) radius $r > 1$.

Q3. Same as Q1, except with $S$ an arbitrary convex body, e.g., a cube.

I feel the answer to Q1 should be Yes, but I am less certain of Q3. Exact computation of probabilities as a function of $n$ might be difficult, but I am hoping there are relatively simple arguments to settle these questions. Thanks for ideas!

Answered (1May13). The combination of Ori Gurel-Gurevich's and Benoît Kloeckner's postings constitute a rather complete answer, establishing that the answer to all my questions is Yes, even without the assumption that $S$ is convex. Thanks for the interest!

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ I thought I had a simple answer, and then it turns out that your question is more interesting than my (incorrect) answer. My idea was to rephrase your connectedness question as follows: is the graph whose vertices are the circles and the edges are the pair of linked circles connected? Then, to use the Erdös-Renyi model for random graphs. With fixed parameter $p$ and $n\to\infty$, the connectedness probability goes to $1$. But the probability of connection between the circles are not independent, so we cannot apply the Erdös-Renyi model. (...) $\endgroup$
    – Benoît Kloeckner
    Commented Apr 27, 2013 at 18:42
  • 1
    $\begingroup$ (...) However, it seems that for any fixed circle, the probability that a random one is linked with it is bounded away from $0$, so there may be a clever coupling argument to use E-R random graphs. My guess is that the answer to all 3 questions is positive, except possibly Q3 when $S$ is lower-dimensional (in fact, a segment is my best bet to provide a negative example to Q3). $\endgroup$
    – Benoît Kloeckner
    Commented Apr 27, 2013 at 18:46
  • $\begingroup$ @Benoît: Yes, I noticed that random graph results seem not to suffice, at least not directly. Excellent point about lower-dimensional $S$! I was implicitly assuming vol$(S) > 0$. $\endgroup$
    – Joseph O'Rourke
    Commented Apr 27, 2013 at 18:56
  • $\begingroup$ According to the description in the tag-wiki, the (geometry) is deprecated. But I do not know enough about this topic to make a reasonable retagging. As this comment is not that relevant for the question itself, you can ping me after you seen it, so that I can delete my comment. (Perhaps pinging me in chat would be better, since it does not leave your comment with a ping here.) Another possibility would be flagging my comment as obsolete. $\endgroup$
    – Martin Sleziak
    Commented Apr 27, 2014 at 6:08
  • $\begingroup$ Related, later question: Tangled random triangles: One giant component?. $\endgroup$
    – Joseph O'Rourke
    Commented May 4, 2018 at 16:46

2 Answers 2

Reset to default
5
$\begingroup$

I think I can complement the answer of Ori Gurel-Gurevich to prove that indeed, when we deal with connected open sets (no need for convexity) the answer is positive.

1. There is a finite configuration of circles $C_1, \dots, C_N$ whose centers are in the domain $D$, such that any circle $C$ with center in the domain $D$ must be linked to at least one of the $C_i$.

One way to do this is to first take a very tight lattice $\Lambda$, and put horizontal circles $C_1,\dots, C_K$ with centers on $\Lambda\cap D$. Now, a circle with center in $D$ that is not linked to any of these $C_i$ ($i\leq K$) must be roughly horizontal.

Then, add circles $C_{K+1},\dots, C_N$ with center on the lattice but oriented along a given vertical plane. A circle not linked to any $C_i$ must be roughly horizontal and roughly vertical, thus don't exist.

2. The above construction is stable under small perturbation. This means that there are small open sets $U_1,\dots, U_N$ of the parameter space such that for all set of circles $C_1,\dots, C_N, C$ such that $C_i\in U_i$, $C$ must be linked to one of the $C_i$.

3. By adding more circles that link together the $C_i$ of 1., we could have assumed that the $C_i$ make a linked component (this is where we use the connectedness assumption on $D$, which in fact could be weakened). As in 2., this is stable under small perturbation, so in fact there are small open sets $U_1,\dots, U_N$ of the parameter space such that for all set of circles $C_1,\dots, C_N, C$ such that $C_i\in U_i$, the $N+1$ circles must be linked together.

4. Now, when $n\to \infty$ the probability that circles have been drawn in each of the $U_i$ increase to $1$ exponentially fast, so at some point our random configuration contains with high probability a set of circles that links all admissible circles, including all the other randomly drawn ones.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Nice idea to arrange that not-linking requires circles that are simultaneously nearly horizontal and nearly vertical! $\endgroup$
    – Joseph O'Rourke
    Commented Apr 28, 2013 at 16:07
  • 1
    $\begingroup$ Actually, I don't see how step 1 works in full generality. For example, if the domain $D$ is a "cone" with a vary pointy tip (not the regular quadratic surface, but one where the angle is 0), then a ring whose center is at the tip and is orthogonal to the cone's axis will not be connected to any ring whose center is inside the cone. However, it seems plausible that this method works for, say, any domain with a smooth boundary. $\endgroup$
    – Ori Gurel-Gurevich
    Commented May 6, 2013 at 17:13
  • $\begingroup$ @Ori Gurel-Gurevich: you are certainly right, I was too optimistic. I guess the method works under certain regularity assumptions (smooth or convex should work). $\endgroup$
    – Benoît Kloeckner
    Commented May 6, 2013 at 18:30
7
$\begingroup$

Cool question!

I believe the answer should be positive for any bounded connected body, but I cannot show this yet. However, I have a reduction of the question to the case where the body is small.

The idea is to partition the body into smaller bodies, say by taking the intersections of the cubic lattice of side length $1/10$ with the body. Then we define a "good event" in every cube saying that there are 3 rings in that cube that are roughly in the directions of the 3 axis. Then, with high probability all the cubes will be good. Now, every 2 adjacent good cubes are necessarily linked (we may have to make the good event have more then just these 3 rings for it to work). Thus, we have a "giant linked component".

Now, it remains to show that if the body is small (relative to the rings) with high probability all the rings are linked. It seems that one needs to analyze the probability that the "extremal rings" are roughly orthogonal to the cluster of centers, but I don't know exactly how to do that.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Great insights, Ori! Especially your point about extremal rings being orthogonal to the cluster of centers. $\endgroup$
    – Joseph O'Rourke
    Commented Apr 27, 2013 at 23:31

You must log in to answer this question.

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