Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
1  
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. (...) –  Benoît Kloeckner Apr 27 '13 at 18:42
1  
(...) 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). –  Benoît Kloeckner Apr 27 '13 at 18:46
    
@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$. –  Joseph O'Rourke Apr 27 '13 at 18:56
    
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. –  Martin Sleziak Apr 27 at 6:08

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer
    
Nice idea to arrange that not-linking requires circles that are simultaneously nearly horizontal and nearly vertical! –  Joseph O'Rourke Apr 28 '13 at 16:07
    
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. –  Ori Gurel-Gurevich May 6 '13 at 17:13
    
@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). –  Benoît Kloeckner May 6 '13 at 18:30

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.

share|improve this answer
    
Great insights, Ori! Especially your point about extremal rings being orthogonal to the cluster of centers. –  Joseph O'Rourke Apr 27 '13 at 23:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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