15
$\begingroup$

Suppose you generate random chords of a circle, with endpoints selected uniformly over the circumference, rejecting any chord that crosses a previously generated chord. The disk is then partitioned into regions bounded by chords alternating with circular arcs. For example, here are $n{=}100$ random noncrossing chords, with a region bounded by 5 chords highlighted (in green).
alt text
I am interested in the statistics of the structure of the dual trees for these regions. Assign each region a node, and connect two nodes by an edge if they share a chord. In the example above, the highlighted region's node has degree 5. Example questions: What is the expected maximum degree of a node for $n$ chords? Making a max-degree node the root, what is the expected height of the tree? (In the example above, the height is 21.) Etc.

Has anyone encountered this model before? Or a model sufficiently analogous to help establish these statistics? Thanks for any pointers!

Edit. Many thanks for the wealth of information provided by the community! So far I have not found the following specific question answered (although it is likely implied, perhaps in the papers they cite): What is the expected maximum degree of a node as $n \rightarrow \infty$? What brought me to this topic in the first place is that I wondered if it might be near 3.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ are you aware of the work by David Aldous on random triangulations of the circle? there's a nice American Mathematical Monthly article of his from 1991 reviewing that construction. He considers triangulations of regular n-gons as n goes to infinity, and chooses triangulations uniformly from that set. in this case the dual trees are binary trees and there is a series of bijections to positive walks from 0 to 2(n-1) which in the large n limit tend to Brownian excursions after rescaling. $\endgroup$
    – j.c.
    Commented Sep 2, 2010 at 13:52
  • $\begingroup$ @jc: No, I was not familiar. Must be this paper: "Triangulating the Circle at Random." Amer. Math. Monthly 101 (1994) 223-233. I will investigate. Thanks! $\endgroup$
    – Joseph O'Rourke
    Commented Sep 2, 2010 at 13:57
  • $\begingroup$ oops, I misstated the result: the positive walks are those starting at 0 and first returning to 0 after 2(n-1) steps of +1 or -1 $\endgroup$
    – j.c.
    Commented Sep 2, 2010 at 14:05

2 Answers 2

Reset to default
12
$\begingroup$

The article "Random recursive triangulations of the disk via fragmentation theory" discusses many properties of the model you describe. The search word is random geodesic lamination.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Ah, thanks! I would never have hit upon "random geodesic laminations"! $\endgroup$
    – Joseph O'Rourke
    Commented Sep 2, 2010 at 13:55
  • 2
    $\begingroup$ The height of that tree is conjectured (by Nicolas Curien in a talk I saw) to be of the order n^{(sqrt(17)-3)/2} -- if you pick two uniformly random nodes, this will be the rough distance between them. But an argument is missing to show that there is no small exceptional set of nodes at greater distance from one another. $\endgroup$
    – Louigi Addario-Berry
    Commented Sep 2, 2010 at 14:21
  • $\begingroup$ @louigi: Cool! That evaluates to approx. 13 for $n{=}100$. $\endgroup$
    – Joseph O'Rourke
    Commented Sep 2, 2010 at 14:34
  • 2
    $\begingroup$ But there are constants. Together Theorem 1.1 (ii) and Proposition 4.1 imply that, viewing the circle as the unit circle in the complex plane, the expected distance from 1 to $e^{2 \pi i u}$ is about $2.0(n u (1-u))^{\beta}$, where $\beta = (\sqrt{17}-3)/2$. (The 2.0 here is a pretty good approximation to what is in fact a ratio of Gamma functions.) This gives expected distance a little over 12 between $1$ and $-1$, for example. $\endgroup$
    – Louigi Addario-Berry
    Commented Sep 2, 2010 at 15:16
8
$\begingroup$

Louigi is absolutely right. We control "typical" height not absolute one. Note that a similar discrete model has been investigated by physicists see http://www.phys.ens.fr/~wiese/pdf/hiraRNA.pdf I think the maximal degree after n steps is logarithmic, but I don't have any exact expression for the expected value...

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Thanks, your paper that Gjergji cited is exactly what I was looking for! I will enjoy learning the source of the magic number $\frac{1}{2} (\sqrt{17} -3)$! $\endgroup$
    – Joseph O'Rourke
    Commented Sep 2, 2010 at 15:09

You must log in to answer this question.

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