Diameter of random segment intersection graph?

Question

I have an even number of points $n$ randomly distributed (uniformly) in a disk. Then the points are randomly connected to form $n/2$ segments, a perfect matching. Finally, I form the intersection graph $G$ whose nodes are the segments, and each of whose edges represents a proper intersection between a pair of segments. An example is shown below:

---

 

---

My question is:

Q. What is the diameter of $G$ as $n \to \infty$?

I have some evidence that the diameter approaches a constant $> 1$, perhaps $4$ or $5$, but to be honest, the evidence is not robust.

---

Added. This may not be helpful, but for $n=1188$, $n_{\mathop{segs}}=n/2=594$, one simulation resulted in $G$ having $37,117$ edges, mean vertex degree $125$, one connected component, and diameter $4$:

---

---

Answer 1

This is not an complete answer but more what you have to prove here. Assume that the model is built by adding two (uniformly distributed) connected points sequentially (n/2 times). Call $p_n$ the probability that the segment formed by the next two points is isolated from the rest. Then if $p=\sum_n p_n=\infty$, you'll have such segments infinitely often, and your diameter will be infinite infinitely often, so no limit, therefore I guess one should have an idea of the value of $p$.

Answer 2

My guess would be that the answer is at most $3$, and probably just $2$. This is because your model should morally behave like an Erdős-Renyi graph for some fixed $p$. These however have typical diameter at most $3$ for large $n$ already if $p \approx n^{-\alpha}$ for any fixed $\alpha < {2\over 3}$. See for example Klee and Larman, Diameters of random graphs.

Answer 3

Here is a way of thinking. It may turn out to be misleading, but it may also suggest a way to think properly about this problem.

Lets take a random instance of a matching and reconstruct it edge by edge. We will start by maximizing the diameter of the intersection graph. To me this means making a large cycle of crossing sticks, so that the intersection graph is a path or a cycle. Suppose we are lucky, and manage to use 2/3 (say) of the sticks to create a subarrangement of (induced) maximal possible diameter.

Now we place the rest of the sticks, which can only decrease the induced diameter. With high probability, the diameter is reduced by a minimum ratio with each new stick or perhaps a small number of new sticks. In any case, I see O(log G) many sticks needed to bring the diameter back down. For large G, this still leaves many sticks left.

It still leaves the possibility that the diameter grows like log log G, but the idea of finding the subconfiguration inducing the largest diameter and then reducing it appeals to me as an inroad to the problem.

Answer 4

I don't have sufficient privileges to add a comment, but I wanted to ask if your evidence is consistent with the conclusion that the diameter of $G$ increases logarithmically with $n$. That would have been my guess.

Added: Perhaps I should have included some rough justification for my guess. In a sense, the diameter measures a worst case scenario. As $n$ increases, the chance that adding a new segment between points in the disk will make things "even worse" should becoming smaller, but alas it seems that things should always be able to get worse, with some finite probability. And so it is difficult for me to believe that diameter of $G$ can be bounded with increasing $n$.

Added: I just realized that my initial guess was silly, since adding segments in the disk can actually decrease the diameter of $G$. If the diameter of $G$ converges as $n$ increases, then I guess there must be some balancing that happens in this regard.