We consider three different schemes for signal routing on a tree. The vertices of the tree represent transceivers that can transmit and receive signals, and are equipped with i.i.d. weights representing the strength of the transceivers. The edges of the tree are also equipped with i.i.d. weights, representing the costs for passing the edges. For each one of our schemes, we derive sharp conditions on the distributions of the vertex weights and the edge weights that determine when the root can transmit a signal over arbitrarily large distances.
 These notes provide an elementary and self-contained introduction to branching ran- dom walks. Section 1 gives a brief overview of Galton-Watson trees, whereas Section 2 presents the classical law of large numbers for branching random walks. These two short sections are not exactly in- dispensable, but they introduce the idea of using size-biased trees, thus giving motivations and an avant-gout to the main part, Section 3, where branching random walks are studied from a deeper point of view, and are connected to the model of directed polymers on a tree. Tree-related random processes form a rich and exciting research subject. These notes cover only special topics. For a general account, we refer to the St-Flour lecture notes of Peres (47) and to the forthcoming book of Lyons and Peres (42), as well as to Duquesne and Le Gall (23) and Le Gall (37) for continuous random trees. 1. Preface 2. Basic Definitions and a Few Highlights 3. Galton-Watson Trees 4. General percolation on a connected graph 5. The First-Moment Method 6. Quasi-independent Percolation 7. The Second Moment Method 8. Electrical Networks 9. Infinite Networks 10. The Method of Random Paths 11. Transience of Percolation Clusters 12. Subperiodic Trees 13. The Random Walks ( RW _ ) 14. Capacity 15. Intersection-Equivalence 16. Reconstruction for the Ising Model on a Tree 17. Unpredictable Paths in Z and EIT inZ2 18. Tree-Indexed Processes 19. Recurrence for Tree-Indexed Markov Chains 20. Dynamical Percolation 21. Stochastic Domination Between Trees Consider randomly scattered radio transceivers in ℝ d , each of which can transmit signals to all transceivers in a given randomly chosen region about itself. If a signal is retransmitted by every transceiver that receives it, under what circumstances will a signal propagate to a large distance from its starting point? Put more formally, place points x i in ℝ d according to a Poisson process with intensity 1. Then, independently for each x i , choose a bounded region A xi from some fixed distribution and let , be the random directed graph with vertex set x i and edges x i -x j whenever x j ∈ x i + A xi . We show that, for any η > 0, g will almost surely have an infinite directed path, provided the expected number of transceivers that can receive a signal directly from x i is at least 1 + η, and the regions x i + A xi do not overlap too much (in a sense that we shall make precise). One example where these conditions hold, and so gives rise to percolation, is in ℝ d , with each A xi a ball of volume 1 + η centred at x i , where η → 0 as d → ∞. Another example is in two dimensions, where the A xi are sectors of angle eθ and area 1 + η, uniformly randomly oriented within a fixed angle (1 + e)θ. In this case we can let η → 0 as e → 0 and still obtain percolation. The result is already known for the annulus, i.e. that the critical area tends to 1 as the ratio of the radii tends to 1, while it is known to be false for the square (l ∞ ) annulus. Our results show that it does however hold for the randomly oriented square annulus. Suppose that i.i.d. random variables are attached to the edges of an infinite tree. When the tree is large enough, the partial sumsSσ along some of its infinite paths will exhibit behavior atypical for an ordinary random walk. This principle has appeared in works on branching random walks, first-passage percolation, and RWRE on trees. We establish further quantitative versions of this principle, which are applicable in these settings. In particular, different notions of speed for such a tree-indexed walk correspond to different dimension notions for trees. Finally, if the labeling variables take values in a group, then properties of the group (e.g., polynomial growth or a nontrivial Poisson boundary) are reflected in the sample-path behavior of the resulting tree-indexed walk. Starting around the late 1950s, several research communities began relating the geometry of graphs to stochastic processes on these graphs. This book, twenty years in the making, ties together research in the field, encompassing work on percolation, isoperimetric inequalities, eigenvalues, transition probabilities, and random walks. Written by two leading researchers, the text emphasizes intuition, while giving complete proofs and more than 850 exercises. Many recent developments, in which the authors have played a leading role, are discussed, including percolation on trees and Cayley graphs, uniform spanning forests, the mass-transport technique, and connections on random walks on graphs to embedding in Hilbert space. This state-of-the-art account of probability on networks will be indispensable for graduate students and researchers alike.