232 R. Brooks
or a bottom, and joining it to another end, again disregarding whether it is
a top or a bottom. One gets∼(1/2) log(n) for the number of components,
as before, but the expected length rises to 2n/3, rather thann/2. A rather
unexpected (at least to me) cancellation of terms arises, similar to the fact
that we always got 1/n, which makes this calculation elementary.
Note that in either case, we have not calculated the expected length of
thelongestloop, but rather the expected length of a loop starting from some
given point. While we expect that this point will tend to lie on a longer rather
than a shorter loop, the expected value of the longest path will be greater.
This gives the improvement from 1/2to. 62 ..., but we prefer the ease of
computation to the sharp constant.
We now consider how to translate this to the estimation of left-hand turn
paths on three-regular oriented graphs. The starting point is to modify the
spaghetti model in the following way: instead of putting downnpieces of
spaghetti, we put downnpieces each of which is a vertex with three half-edge
(Fig. 12.12):
We will find it convenient to draw on these pieces the corresponding pieces
of LHT paths.
The process of picking up an end and gluing it to another end is exactly the
Bollobas model, modified by labeling the balls so as to get a cyclic ordering.
We now want to make the same calculation we did before. When we pick
up an end, what are the probabilities of forming a closed LHT path when we
pick another end?
We may make the same calculation as before: look at the end we have
picked up, and follow the two LHT path segments leading from it, until you
arrive at two endpoints (which may be the same point). It would therefore
appear that the expected value of the number of closed LHT paths produced
would be 2 divided by the number of remaining edges, which in turn would
give an estimate of∼log(n) for the expected number of LHT paths.
The problem with this argument arises in the following picture:
If one LHT path starting at an end wraps around and finishes at the same
end, then we call this end abottleneck (Fig. 12.13). If two bottlenecks are
joined together, then a closed LHT path is formed. Thus, the probability of
forming a closed
1bR1aR1cL1aL1bL1cR2bR2aR2cL2aL2bL2cR3bR3aR3cL3aL3bL3cR
Fig. 12.12.Modified spaghetti