9
$\begingroup$

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:


  SegSegInt
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$:
SigIntGraph


$\endgroup$
5
  • $\begingroup$ The matching is uniform over all possible matchings? $\endgroup$ – kaleidoscop Jun 11 '15 at 16:55
  • $\begingroup$ @kaleidoscop: The two endpoints to connect with a segment are chosen randomly and uniformly among the points not yet connected. This process is continued to the final two unconnected points. $\endgroup$ – Joseph O'Rourke Jun 11 '15 at 16:56
  • $\begingroup$ Ok, then I guess it's equivalent to the uniform matching. You want to prove the limit exists? You want the exact value? Or just that the limsup is bounded? $\endgroup$ – kaleidoscop Jun 11 '15 at 17:15
  • $\begingroup$ @kaleidoscop: All three, s'il vous plaît :-). More seriously, any insights would help. Thanks for your interest! $\endgroup$ – Joseph O'Rourke Jun 11 '15 at 17:22
  • $\begingroup$ By the way I think the graph on the right is called a "random intersection graph" in the literature, you might want to search with this key-word (see today's arxiv post arxiv.org/abs/1506.03389). $\endgroup$ – kaleidoscop Jun 11 '15 at 18:11
3
$\begingroup$

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$.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Citation of paper referenced: Klee, Victor, and David Larman. "Diameters of random graphs." Canad. J. Math 33 (1981): 618-640. (Paper link.) $\endgroup$ – Joseph O'Rourke Jun 11 '15 at 23:24
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Yes, Menachem. I haven't implemented a sufficiently efficient simulation to test for large $n$. $\endgroup$ – Joseph O'Rourke Jun 11 '15 at 19:35

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.