ON GENERALIZED RANDOM RAILWAYS

HANS GARMO, SVANTE JANSON, AND MICHAŁ KAROŃSKI

Abstract. We consider a random generalized railway defined as a random 3-regular multigraph where some vertices are regarded as switches that only allow traffic between certain pairs of attached edges. It is shown that the probability that the generalized railway is functioning is linear in the proportion of switches. Thus there is no threshold phenomenon for this property.

1. Introduction

A railway is a 3-regular multigraph where each vertex is regarded as a switch where one of the attached edges is regarded as a main track that branches into the two others. Thus, a train that approaches a vertex along the main track (for that vertex) can continue on any of the two other tracks, but a train coming on one of the branching tracks has to leave the vertex on the main track.

A random railway is a random 3-regular multigraph where each vertex is regarded as a switch in a randomly chosen orientation. Random railways were introduced and studied by Garmo [6], where the reader also can find examples and a historical background.

Railways can be regarded as a special case of multigraphs with restrictions on the connections at each vertex; we may at each vertex of a multigraph impose any set of rules allowing passage from one edge only to certain others. In other words, instead of the usual line graph of a multigraph G (or its directed version), we consider a certain subgraph of it. Other such (multi)graphs with restrictions have been considered by Andersson [1] and Janson and Wormald [9], but will not be considered here.

A railway is functioning if a train starting on an arbitrary edge in an arbitrary direction, can reach any other edge while obeying the rule above at each vertex.

Remark 1. A stronger requirement is that a train starting on an arbitrary edge in an arbitrary direction can reach any other edge in any other direction. Such railways are said to be two-way functioning [6]. In other words, a railway is two-way functioning if the corresponding restricted directed edge graph is strongly connected. As is shown in [6], the probability that a random railway is functioning but not two-way functioning decreases exponentially. The same applies to the generalization studied here; thus the results below hold without changes if “functioning” is replaced by “two-way functioning”.

Date: February 20, 2002; revised January 21, 2003.

Garmo [6] showed that the probability that a random railway with n vertices is functioning converges to 1/3 as n → ∞. (Since the number of vertices in a 3-regular multigraph is even, we assume throughout the paper that n is even without further comment.) On the other hand, if we consider a random 3-regular multigraph without restrictions, it is a.a.s. functioning, i.e. functioning with probability tending to 1 as n → ∞. Indeed, it is easy to see that a 3-regular multigraph is functioning if and only if it is connected, which holds a.a.s., see e.g. [2]. The purpose of the present paper is to study the transition between these cases by considering intermediate cases where we mix switches and ordinary vertices.

We define the generalized random railway R_{n,p} to be a random 3-regular multigraph on n vertices where each vertex with probability p is replaced by a switch in a random orientation, all random choices being independent. The remaining vertices, which are not made into switches, allow traffic from any edge to any other edge. Alternatively, we could start with a random railway and randomly, with probability 1 − p, replace switches by “superswitches” allowing traffic from any edge to any other. Hence, R_{n,1} is the random railway considered by Garmo, while R_{n,0} is just a random 3-regular multigraph. The results just given for these extreme cases connect in the following way.

Theorem. Let 0 ≤ p ≤ 1 be fixed. Then, as n → ∞,

ℙ(R_{n,p} is functioning) → 1 − 2p/3.

We thus have a smooth linear transition as p varies between 0 and 1. This is in contrast with the behaviour of many properties of random graphs (or random subsets in general), where there is a sharp threshold; see e.g. [4], [3] for early examples and results and [8] for a survey. In particular, Friedgut [5] has shown that a property of random subsets, or random graphs, has a sharp threshold unless the property only depends on small subsets, or can be approximated in a certain sense by such a “local” property. In view of this, the result above is somewhat surprising, since “functioning” is a global property. There are two explanations for this behavior. First, the random replacement of vertices by switches yields a random subset as in Friedgut’s theorem, but there are other random factors too, viz. the underlying random 3-regular multigraph and the orientation of the switches, which may blur the threshold. Secondly, and more importantly, as is shown in [6], see the proof below, the global property of “functioning” is essentially (i.e. approximately) determined by the local property “there are no paddle wheels”. Friedgut [5] has given simple artificial examples where a global property is essentially determined by a local property. This paper exhibits an example, although in a more complicated situation, showing that the same can happen for natural global properties, which stresses the need for the rather complicated

Figure 1. A paddle wheel

arguments used in various applications of Friedgut’s theorem to specific properties.

Remark. We clearly obtain the same asymptotical result if we consider random 3-regular multigraphs with fixed numbers of switches and ordinary vertices (superswitches).

Remark. Another interesting problem is whether R_{n,p} is hamiltonian, i.e. has an allowed cycle through all vertices. For p = 0, the probability of this tends to 1/e. Indeed, Robinson and Wormald [10] showed that a random 3-regular simple graph is a.a.s. hamiltonian; their proof extends to showing that a random 3-regular multigraph is a.a.s. hamiltonian if and only if it lacks loops, see [8]. For p ≥ 3(1 − \sqrt{3}/2) ≐ 0.402, the first moment method (a simple calculation of the expected number of hamilton cycles) shows that the probability tends to 0. For smaller p > 0, we do not know. (We conjecture a sharp threshold.)

2. Proof of the theorem

We use the construction of R_{n,p} where we start with a random railway R with n vertices and with probability 1 − p replace switches by superswitches (ordinary vertices). Clearly, if the railway R is functioning then so is R_{n,p}, since we only have added more connections.

As is shown in [6], the main obstruction to R being functioning is the presence of paddle wheels, where a k-paddle wheel (k ≥ 1) is a set of k switches connected in a cycle such that the main track of each is connected to one of the branching tracks of the next switch; see Figure 1. It is evident that the presence of a paddle wheel implies that the railway is malfunctioning, since a train entering the paddle wheel is trapped there. Conversely, see [6],

ℙ(R is malfunctioning but has no paddle wheels) → 0

because the probability of the existence of some other trapping configuration in a random railway tends to 0. In other words, a random railway is, a.a.s., functioning if and only if it contains no paddle wheels. Furthermore, see again [6], the number of paddle wheels is asymptotically Poisson distributed; more precisely, if X_{k} is the number of k-paddle wheels in R, then

X_{k} →^{d} Po(\frac{1}{k} (\frac{2}{3})^{k}),  (1)

Figure 2. A paddle wheel with some trees leading to it

jointly for all k ≥ 1. Moreover, we have the uniform bound

𝔼 X_{k} ≤ (\frac{4}{5})^{k},  (2)

which enables us to sum (1) over all k by a truncation argument [6]. Hence, for the total number of paddle wheels in R,

∑_{k} X_{k} →^{d} Po(∑_{k=1}^{∞} \frac{1}{k} (\frac{2}{3})^{k}) = Po(ln 3).

In order to extend these results to R_{n,p}, we use further the structure result of [7], which shows that, a.a.s., if the random railway R has m ≥ 0 paddle wheels W_{1}, …, W_{m}, then the edge set of R can be partitioned in a large set E_{0} and sets E_{1}, …, E_{m}, where E_{0} is functioning in the sense that a train starting on any edge in E_{0} in any direction can reach any other edge in E_{0}, while E_{i}, i = 1, …, m, contains the edges such that a train starting there in a certain direction gets trapped by W_{i} (if it starts on an edge in E_{i} in the other direction it can always reach E_{0}). If W_{i} is a k-paddle wheel, then the set E_{i} contains the k edges in W_{i}, the k edges leading in to it, and possibly some further edges forming small trees attached to W_{i}; see Figure 2. Moreover, any edge may be reached from some, and thus from every, edge in E_{0}.

Now suppose that R is of this type and that we change it into R′, say, by converting some switches into ordinary vertices, thus adding another possible connection through some vertices. It is obvious that if some paddle wheel remains, then a train entering the paddle wheel is trapped and R′ is not functioning. On the other hand, it is equally obvious that if no paddle wheel remains, which means that at least one switch in each paddle wheel is replaced by an ordinary vertex, then a train reaching W_{i} may, through the new connection, find its way back to E_{0}. Consequently, R′ then is functioning.

In particular, doing the random substitution giving R_{n,p}, we see that R_{n,p} is a.a.s. functioning if and only if it contains no paddle wheels, and thus

ℙ(R_{n,p} has no paddle wheels) − ℙ(R_{n,p} is functioning) → 0.  (3)

Finally, a k-paddle wheel in R has probability p^{k} to survive to R_{n,p}, so if X_{k,p} is the number of k-paddle wheels in R_{n,p}, then it follows immediately from (1) that

X_{k,p} →^{d} Po(\frac{1}{k} (\frac{2}{3})^{k}p^{k}),

jointly for all k ≥ 1. The bound (2) again enables us to sum this and obtain

∑_{k} X_{k,p} →^{d} Po(∑_{k=1}^{∞} \frac{1}{k} (\frac{2p}{3})^{k}) = Po(− ln(1 − 2p/3)).

Consequently,

ℙ(R_{n,p} has no paddle wheels) = ℙ(∑_{x} X_{k,p} = 0)
→ exp(ln(1 − 2p/3)) = 1 − 2p/3,

and the theorem follows by (3). □

Acknowledgement. We thank Pontus Andersson for pointing out an error in a preliminary version of this paper.

References

[1] P. Andersson, Hamilton cycles in generalized random railways. In preparation.

[2] B. Bollobás, Random Graphs, 2nd ed., Cambridge Univ. Press, 2001.

[3] B. Bollobás & A. Thomason, Threshold functions. Combinatorica 7 (1987), 35–38.

[4] P. Erdős & A. Rényi, On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci. 5 (1960), 17–61.

[5] E. Friedgut, Sharp thresholds of graph properties, and the k-sat problem. J. Amer. Math. Soc. 12 (1999), 1017–1054.

[6] H. Garmo, Random railways as 3-regular graphs. Random Structures Algorithms 9 (1996), no. 1–2, 113–136.

[7] H. Garmo, Asymptotic properties of the connectivity number of random railways. Adv. Appl. Probab. 31 (1999), no. 3, 720–741.

[8] S. Janson, T. Łuczak & A. Ruciński, Random Graphs. Wiley, New York, 2000.

[9] S. Janson & N.C. Wormald, Rainbow hamilton cycles in random regular graphs. In preparation.

[10] R.W. Robinson & N.C. Wormald, Almost all cubic graphs are hamiltonian. Random Structures Algorithms 3 (1992), 117–125.

Department of Mathematics, Uppsala University, PO Box 480, S-751 06 Uppsala, Sweden

E-mail address: hans.garmo@math.uu.se

Department of Mathematics, Uppsala University, PO Box 480, S-751 06 Uppsala, Sweden

E-mail address: svante.janson@math.uu.se
URL: http://www.math.uu.se/~svante/

Department of Discrete Mathematics, Adam Mickiewicz University, Poznań, Poland and

Department of Mathematics and Computer Science, Emory University, Atlanta, USA

E-mail address: karonski@amu.edu.pl,   michal@mathcs.emory.edu
URL: http://main.amu.edu.pl/~karonski/