UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Discrete probability and the geometry of graphs Hutchcroft, Thomas 2017

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
24-ubc_2017_september_hutchcroft_thomas.pdf [ 6.47MB ]
Metadata
JSON: 24-1.0354251.json
JSON-LD: 24-1.0354251-ld.json
RDF/XML (Pretty): 24-1.0354251-rdf.xml
RDF/JSON: 24-1.0354251-rdf.json
Turtle: 24-1.0354251-turtle.txt
N-Triples: 24-1.0354251-rdf-ntriples.txt
Original Record: 24-1.0354251-source.json
Full Text
24-1.0354251-fulltext.txt
Citation
24-1.0354251.ris

Full Text

Discrete probability and the geometryof graphsbyThomas HutchcroftB.A., University of Cambridge, 2012M.Math., University of Cambridge, 2013M.A., University of Cambridge, 2016A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFDOCTOR OF PHILOSOPHYinThe Faculty of Graduate and Postdoctoral Studies(Mathematics)THE UNIVERSITY OF BRITISH COLUMBIA(Vancouver)August 2017c© Thomas Hutchcroft 2017AbstractWe prove several theorems concerning random walks, harmonic functions, percolation, uniformspanning forests, and circle packing, often in combination with each other. We study these mod-els primarily on planar graphs, on transitive graphs, and on unimodular random rooted graphs,although some of our results hold for more general classes of graphs. Broadly speaking, we areinterested in the interplay between the geometry of a graph and the behaviour of probabilisticprocesses on that graph. Material taken from a total of nine papers is included. We have alsoincluded an extended introduction explaining the background and context to these papers.iiLay SummaryThere is a deep and well-developed connection between the geometry of a space and the wayprobabilistic processes behave on that space. A classical example is given by a heavy particle (e.g.a mote of dust) that moves randomly through space due to its bumping into a large number oflight particles (e.g., air molecules): The particle will move much faster in negatively curved spacesthan in flat space. In this thesis we continue to develop this connection in a discrete setting, whereour spaces are modeled by graphs. We prove several new results connecting the geometry of agraph to the behaviour of random processes on it. We are particularly interested in random walk,a discrete version of the random motion mentioned above, percolation, which models a randomporous material, and the uniform spanning forest, a probability model that is closely connected tothe theory of electrical networks.iiiPreface• Chapter 2 is adapted from the paper Critical percolation on any quasi-transitive graph ofexponential growth has no infinite clusters [129], of which I am the only author. This paperwas published in Comptes Rendus Mathematique in 2016.• Chapter 3 is adapted from the paper Collisions of random walks in reversible random graphs[133], by Yuval Peres and myself. Research was conducted as an equal collaboration, while Idid most of the writing. This paper was published in Electronic Communications in Proba-bility in 2015.• Chapter 4 is adapted from the paper Wired cycle-breaking dynamics for uniform spanningforests [127], of which I am the only author. This paper was accepted for publication in TheAnnals of Probability in 2015.• Chapter 5 is adapted from the preprint Interlacements and the wired uniform spanning forest[128], of which I am the only author. This paper was accepted for publication in The Annalsof Probability in 2017.• Chapter 6 is adapted from the paper Indistinguishability of trees in uniform spanning forests[131], by Asaf Nachmias and myself. Research was conducted as an equal collaboration, whileI did most of the writing. The paper was accepted for publication in Probability Theory andRelated Fields in 2016.• Chapter 7 is adapted from the paper Unimodular hyperbolic triangulations: circle packing andrandom walk [21], by Omer Angel, Asaf Nachmias, Gourab Ray, and myself. Research wasconducted as an equal collaboration, while I did most of the writing. The paper appeared inInventiones Mathematicae in 2016.• Chapter 8 is adapted from the preprint Boundaries of planar graphs: a unified approach [132],by Yuval Peres and myself. Research was conducted as an equal collaboration, while I didmost of the writing. The paper was accepted for publication in The Electronic Journal ofProbability in 2017.• Chapter 9 is adapted from the preprint Hyperbolic and parabolic unimodular random maps[20], by Omer Angel, Asaf Nachmias, Gourab Ray, and myself. Research was conducted asan equal collaboration, while I did most of the writing. The preprint has been submitted forpublication.ivPreface• Chapter 10 is adapted from the preprint Uniform spanning forests of planar graphs [130], byAsaf Nachmias and myself. Research was conducted as an equal collaboration, while I didmost of the writing. The preprint has been submitted for publication.• Chapter 1, the introduction, contains small amounts of the material from all the other chap-ters.vTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiiAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xivDedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xv1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 What is this thesis about? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Random walks on graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2.1 The Nash-Williams Criterion and electrical networks . . . . . . . . . . . . . 21.2.2 The isoperimetric approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.2.3 Bounded harmonic functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.2.4 The Poisson boundary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111.2.5 Infinite electrical networks and harmonic Dirichlet functions . . . . . . . . . 121.3 Circle packing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141.3.1 Planar graphs and maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141.3.2 Circle packing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151.3.3 Harmonic Dirichlet functions on planar graphs . . . . . . . . . . . . . . . . . 211.3.4 Double circle packing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231.3.5 Circle packing and the degree . . . . . . . . . . . . . . . . . . . . . . . . . . 251.4 Percolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261.4.1 The number of infinite clusters . . . . . . . . . . . . . . . . . . . . . . . . . . 281.4.2 The geometry of infinite clusters . . . . . . . . . . . . . . . . . . . . . . . . . 311.5 Uniform spanning forests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321.5.1 Uniform spanning trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331.5.2 Sampling using random walks . . . . . . . . . . . . . . . . . . . . . . . . . . 34viTable of Contents1.5.3 Uniform spanning forests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351.5.4 The number of trees in the wired forest . . . . . . . . . . . . . . . . . . . . . 361.5.5 Geometry of trees in the wired forest . . . . . . . . . . . . . . . . . . . . . . 381.5.6 The interlacement Aldous-Broder algorithm . . . . . . . . . . . . . . . . . . 411.5.7 Indistinguishability of trees and the geometry of trees in the free forest . . . 431.5.8 Uniform spanning forests of planar graphs . . . . . . . . . . . . . . . . . . . 451.5.9 USFs of multiply-connected planar maps . . . . . . . . . . . . . . . . . . . . 461.6 Unimodular random graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 481.6.1 Reversibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 491.6.2 Invariant amenability and nonamenability . . . . . . . . . . . . . . . . . . . 501.6.3 Unimodular random planar maps . . . . . . . . . . . . . . . . . . . . . . . . 511.6.4 The dichotomy theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 531.6.5 Boundary theory of unimodular random triangulations . . . . . . . . . . . . 561.7 Open problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57I Two Short Papers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 592 Critical percolation on any quasi-transitive graph of exponential growth has noinfinite clusters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 602.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 602.2 Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 623 Collisions of random walks in reversible random graphs . . . . . . . . . . . . . . 643.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 643.1.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 653.2 Proof of Theorem 3.1.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 673.3 Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 683.3.1 Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 683.3.2 Continuous-time random walk . . . . . . . . . . . . . . . . . . . . . . . . . . 68II Uniform Spanning Forests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 704 Wired cycle-breaking dynamics for uniform spanning forests . . . . . . . . . . . 714.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 714.1.1 Consequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 734.2 The wired uniform spanning forest . . . . . . . . . . . . . . . . . . . . . . . . . . . . 734.3 Wired cycle-breaking dynamics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 754.3.1 Update-tolerance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 794.4 Proof of Theorem 4.1.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79viiTable of Contents4.5 Reversible random networks and the proof of Theorem 4.1.1 . . . . . . . . . . . . . 815 Interlacements and the wired uniform spanning forest . . . . . . . . . . . . . . . 845.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 845.2 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 865.2.1 Ends . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 865.2.2 Excessive ends . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 885.2.3 Ends in unimodular random rooted graphs . . . . . . . . . . . . . . . . . . . 895.3 Background and definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 905.3.1 Uniform spanning forests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 905.3.2 The space of trajectories . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 905.3.3 The interlacement process . . . . . . . . . . . . . . . . . . . . . . . . . . . . 915.3.4 Hitting probabilities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 935.4 Interlacement Aldous-Broder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 965.5 Proof of Theorems 5.2.1, 5.2.2 and 5.2.4 . . . . . . . . . . . . . . . . . . . . . . . . . 985.5.1 Unimodular random rooted graphs . . . . . . . . . . . . . . . . . . . . . . . 1015.5.2 Excessive ends . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1025.6 Ends and rough isometries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1035.7 Closing discussion and open problems . . . . . . . . . . . . . . . . . . . . . . . . . . 1055.7.1 The FMSF of the interlacement ordering . . . . . . . . . . . . . . . . . . . . 1055.7.2 Exceptional times . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1065.7.3 Excessive ends via update tolerance . . . . . . . . . . . . . . . . . . . . . . . 1095.7.4 Ends in uniformly transient networks . . . . . . . . . . . . . . . . . . . . . . 1096 Indistinguishability of trees in uniform spanning forests . . . . . . . . . . . . . . 1106.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1106.1.1 About the proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1136.1.2 Background and definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1146.1.3 Component properties and indistinguishability on unimodular random rootednetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1186.2 Indistinguishability of FUSF components . . . . . . . . . . . . . . . . . . . . . . . . 1226.2.1 Cycle breaking in the FUSF . . . . . . . . . . . . . . . . . . . . . . . . . . . 1226.2.2 All FUSF components are transient and infinitely-ended . . . . . . . . . . . 1246.2.3 Pivotal edges for the FUSF . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1276.2.4 Proof of Theorem 6.1.9 for the FUSF . . . . . . . . . . . . . . . . . . . . . . 1286.3 The FUSF is either connected or has infinitely many components . . . . . . . . . . 1316.4 Indistinguishability of WUSF components . . . . . . . . . . . . . . . . . . . . . . . . 1346.4.1 Indistinguishability of WUSF components by tail properties. . . . . . . . . . 1346.4.2 Indistinguishability of WUSF components by non-tail properties. . . . . . . 139viiiTable of ContentsIII Circle Packing and Planar Graphs . . . . . . . . . . . . . . . . . . . . . . . . . 1497 Unimodular hyperbolic triangulations: circle packing and random walk . . . . 1507.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1517.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1547.3 Background and definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1567.3.1 Unimodular random graphs and maps . . . . . . . . . . . . . . . . . . . . . . 1567.3.2 Random walk, reversibility and ergodicity . . . . . . . . . . . . . . . . . . . 1577.3.3 Invariant amenability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1597.3.4 Circle packings and vertex extremal length . . . . . . . . . . . . . . . . . . . 1627.4 Characterisation of the CP type . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1657.4.1 Completing the proof of the Benjamini-Schramm Theorem . . . . . . . . . . 1667.5 Boundary theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1687.5.1 Convergence to the boundary . . . . . . . . . . . . . . . . . . . . . . . . . . 1697.5.2 Full support and non-atomicity of the exit measure . . . . . . . . . . . . . . 1717.5.3 The unit circle is the Poisson boundary . . . . . . . . . . . . . . . . . . . . . 1747.6 Hyperbolic speed and decay of radii . . . . . . . . . . . . . . . . . . . . . . . . . . . 1787.7 Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1807.8 Open problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1828 Boundaries of planar graphs: a unified approach . . . . . . . . . . . . . . . . . . . 1848.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1848.1.1 Circle packing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1858.1.2 Robustness under rough isometries . . . . . . . . . . . . . . . . . . . . . . . 1878.1.3 The Martin boundary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1888.2 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1908.2.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1908.2.2 Embeddings of planar graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 1908.2.3 Square tiling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1908.3 The Poisson boundary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1918.3.1 Proof of Theorem 8.1.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1968.4 Identification of the Martin boundary . . . . . . . . . . . . . . . . . . . . . . . . . . 2019 Hyperbolic and parabolic unimodular random maps . . . . . . . . . . . . . . . . 2059.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2059.1.1 The Dichotomy Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2079.1.2 Unimodular planar maps are sofic . . . . . . . . . . . . . . . . . . . . . . . . 2119.2 Unimodular maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2119.2.1 Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2119.2.2 Unimodularity and the mass transport principle . . . . . . . . . . . . . . . . 213ixTable of Contents9.2.3 Reversibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2169.2.4 Ergodicity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2169.2.5 Duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2179.3 Percolations and invariant amenability . . . . . . . . . . . . . . . . . . . . . . . . . 2189.3.1 Markings and percolations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2189.3.2 Amenability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2199.3.3 Hyperfiniteness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2209.3.4 Ends . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2219.3.5 Unimodular couplings and soficity . . . . . . . . . . . . . . . . . . . . . . . . 2229.3.6 Vertex extremal length and recurrence of subgraphs . . . . . . . . . . . . . . 2269.4 Curvature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2279.4.1 Curvature of submaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2309.4.2 Invariance of the curvature . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2339.5 Spanning forests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2379.5.1 Uniform spanning forests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2379.5.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2409.5.3 Proof of Theorem 9.5.13 and Theorem 9.5.16 . . . . . . . . . . . . . . . . . . 2429.5.4 Finite expected degree is needed . . . . . . . . . . . . . . . . . . . . . . . . . 2459.5.5 Percolation and minimal spanning forests . . . . . . . . . . . . . . . . . . . . 2469.5.6 Expected degree formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2489.6 The conformal type . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2509.7 Multiply-connected and non-planar maps . . . . . . . . . . . . . . . . . . . . . . . . 2579.7.1 The topology of unimodular random rooted maps. . . . . . . . . . . . . . . . 2579.7.2 Theorem 9.1.1 in the multiply-connected planar case . . . . . . . . . . . . . 2619.8 Open problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2639.8.1 Rates of escape of the random walk . . . . . . . . . . . . . . . . . . . . . . . 2639.8.2 Positive harmonic functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 26410 Uniform spanning forests of planar graphs . . . . . . . . . . . . . . . . . . . . . . . 26510.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26510.1.1 Universal USF exponents via circle packing . . . . . . . . . . . . . . . . . . . 26710.2 Background and definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27110.2.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27110.2.2 Uniform Spanning Forests . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27110.2.3 Random walk, effective resistances . . . . . . . . . . . . . . . . . . . . . . . . 27410.2.4 Plane Graphs and their USFs . . . . . . . . . . . . . . . . . . . . . . . . . . 27710.2.5 Circle packing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27810.3 Connectivity of the FUSF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27910.3.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27910.3.2 Proof of Theorem 10.1.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282xTable of Contents10.3.3 The FUSF is connected. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28610.4 Critical Exponents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28610.4.1 The Ring Lemma for double circle packings . . . . . . . . . . . . . . . . . . 28610.4.2 Good embeddings of planar graphs . . . . . . . . . . . . . . . . . . . . . . . 28810.5 Critical exponents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28910.5.1 The ring lemma for double circle packings . . . . . . . . . . . . . . . . . . . 28910.5.2 Good embeddings of planar graphs . . . . . . . . . . . . . . . . . . . . . . . 29110.5.3 Preliminary estimates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29310.5.4 Wilson’s algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29810.5.5 Proof of Theorems 10.1.3, 10.1.4 and 10.1.5 . . . . . . . . . . . . . . . . . . . 29910.5.6 The uniformly transient case . . . . . . . . . . . . . . . . . . . . . . . . . . . 30510.6 Closing remarks and open problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 30710.6.1 Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30710.6.2 Open problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309xiList of Figures1.1 Z2 and the 3-regular tree. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.2 Free and wired boundary conditions on a 6× 6 square in Z2. . . . . . . . . . . . . . 131.3 Different maps with the same underlying graph. . . . . . . . . . . . . . . . . . . . . . 151.4 A finite planar map and its dual. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151.5 Circle packings of the 6-regular and 7-regular triangulations. . . . . . . . . . . . . . 171.6 A polyhedral planar map and its double circle packing. . . . . . . . . . . . . . . . . . 241.7 The grandparent graph. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271.8 Two bounded degree, simple, proper plane triangulations for which the graph dis-tance is not comparable to the hyperbolic distance. . . . . . . . . . . . . . . . . . . . 461.9 Circle packings in multiply-connected circle domains. . . . . . . . . . . . . . . . . . . 471.10 The logical structure for the proof of Theorem 9.1.1 in the simply connected case. . 554.1 Updating an oriented spanning forest . . . . . . . . . . . . . . . . . . . . . . . . . . . 764.2 Illustration of the proof of Theorem 4.1.3. . . . . . . . . . . . . . . . . . . . . . . . . 805.1 A schematic illustration of the proof of Lemma 5.5.1. . . . . . . . . . . . . . . . . . . 995.2 An illustration of the graph G32. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1046.1 Illustration of the proof of Lemma 6.2.6. . . . . . . . . . . . . . . . . . . . . . . . . . 1266.2 Illustration of the forest FR and the event CR,n. . . . . . . . . . . . . . . . . . . . . . 1367.1 A circle packing of a random hyperbolic triangulation. . . . . . . . . . . . . . . . . . 1507.2 Geodesic embeddings induced by circle packing. . . . . . . . . . . . . . . . . . . . . . 1647.3 An illustration of the mass transport used to show the exit measure has full support. 1747.4 Illustration of the proof of item 3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1777.5 Extracting the core of a non-simple map. . . . . . . . . . . . . . . . . . . . . . . . . 1818.1 The square tiling and the circle packing of the 7-regular hyperbolic triangulation. . . 1868.2 Illustration of the proof of Theorem 8.1.1. . . . . . . . . . . . . . . . . . . . . . . . . 1959.1 The logical structure for the proof of Theorem 9.1.1 in the simply connected case. . 2099.2 The numbers of the theorems, propositions, lemmas and corollaries forming theindividual implications used to prove Theorem 9.1.1 in the simply connected case. . 2109.3 Different maps with the same underlying graph. . . . . . . . . . . . . . . . . . . . . . 213xiiList of Figures9.4 Examples of verices with positive, zero, and negative curvature. . . . . . . . . . . . . 2299.5 Illustration of the map M1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2329.6 The maps T4 (left) and M4 (right). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2459.7 The covering of Ue by discs used in the proof of Lemma 9.6.2. . . . . . . . . . . . . . 2559.8 Possible topologies of a unimodular random map. . . . . . . . . . . . . . . . . . . . . 25710.1 A simple, 3-connected, finite plane graph and its double circle packing. . . . . . . . . 26810.2 Two bounded degree, simple, proper plane triangulations for which the graph dis-tance is not comparable to the hyperbolic distance. . . . . . . . . . . . . . . . . . . . 26910.3 Illustration of the proof of Theorem 10.1.2 in the case that T is CP hyperbolic. Left: On the eventBeε , the paths ηx and ηy split Vε into two pieces, L and R. Right: We define a random set containinga path (solid blue) from ηx to ηy ∪ {∞} in G \ C using a random circle (dashed blue). Here wesee two examples, one in which the path ends at ηy, and the other in which the path ends at theboundary (i.e., at infinity). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28410.4 Proof of the Double Ring Lemma. If two dual circles are close but do not touch, there must bemany primal circles contained in the crevasse between them. This forces the two dual circles to eachhave large degree. The right-hand figure is a magnification of the left-hand figure. . . . . . . . . 28710.5 Proof of the Double Ring Lemma. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29110.6 The double circle packing of N× Z4. . . . . . . . . . . . . . . . . . . . . . . . . . . . 307xiiiAcknowledgementsFirst and foremost, I thank my advisors Omer Angel and Asaf Nachmias for guiding me throughthe early stages of my research, introducing me to the field, sharing problems and ideas, readingdrafts, and providing me with many opportunities to meet and collaborate with others. I wouldalso like to thank my Microsoft Research mentors Ander Holroyd and Yuval Peres for severalvery enjoyable and productive summers in Redmond, which were hugely beneficial to me. I alsothank Microsoft Research for supporting me financially in the final year of my doctoral studiesby awarding me the Microsoft Research PhD Fellowship. I also thank my collaborators OmerAngel, Nicolas Curien, Ander Holroyd, Avi Levy, Asaf Nachmias, Yuval Peres, and Gourab Rayfor all the stimulating conversations and discoveries we have had together. I hope for many moreto come. I also thank Russ Lyons and Yuval Peres for writing their wonderful book [173], whichI refer to at least once a week, and Itai Benjamini for sending me many interesting questions. Ialso thank everyone who has been a member of the UBC probability group during my time here,especially my fellow students and visiting students: Owen Daniel, Mallory Flynn, Spencer Frei,Tyler Helmuth, Sara´ı Herna´ndez-Torres, Jieliang Hong, Thomas Hughes, Tim Jaschek, MatthiasKlo¨ckner, Brett Kolesnik, Hongliang Lu, Guillermo Mart´ınez Dibene, Gourab Ray, Saif Syed, AlexTomberg, Ben Wallace, Zichun Ye, Jing Yu, and Qingsan Zhu; I could not have asked for a bettergroup of colleagues, peers, and friends.Finally, although I never had the privilege to meet him, I would like to thank Oded Schramm,whose mathematical work, ingenuity, and vision has been a constant inspiration to me. His influenceis felt throughout essentially every subject touched on in this thesis, and it is no coincidence that hisname appears more than 250 times in this thesis, an average of once every 1.4 pages. Throughoutmy work, and especially in my joint work with Asaf, whenever we were unsure how best to approachsomething, it became routine to ask ourselves “What would Oded do?” Reflecting on this questionalways helped us cut right to the heart of the matter at hand, even if we could not always live upto the aspiration of doing things quite as elegantly as he would have.xivTo Meghan, my family and friends.xvChapter 1Introduction1.1 What is this thesis about?This thesis is a collection of papers about discrete probability on infinite graphs. The central themecan be summarised by the following question.What does the geometry of a graph tell us about the behaviour of probabilistic processes on thatgraph? Conversely, what does the behaviour of probabilistic processes on a graph tell us about theunderlying geometry?This question has formed an important strand of thought through modern probability theorysince its inception in the early 20th century. In this introduction, we will take a quick tour throughthe highlights of this tradition. Some of the results of this thesis will be presented as we go, althoughmost of our own contributions will be presented towards the end. Our aim is to present some ofthe main ideas underlying the field, and our own work, in a way that is hopefully accessible to ageneral mathematical audience, without getting too much into technical details.1.2 Random walks on graphsA graph G = (V,E) is a set of vertices V and a set of edges E. We think of vertices as points,and of edges as curves, each of which is either a loop starting and ending at the same point, orelse joins two points together. (More formally, we have an incidence relation which assigns toeach edge either one or two vertices, which are the endpoints of the edge.) For simplicity, we shallconsider in this section only simple graphs, that have no self-loops and at most one edge betweeneach two vertices. A graph is connected if we can pass from any vertex to any other vertex bymoving across a finite sequence of edges. The degree of a vertex is the number of edges incidentto it. We will assume throughout that our graphs have countably many vertices and edges, and arelocally finite, meaning that all the degrees are finite.The random walk on a graph is the process that, at each time n ≥ 0, chooses an edge uniformlyat random from among those incident to its current location, independently from everything it hasdone previously, and then moves to the vertex at the other endpoint of that edge. When we havesome graph in mind, we write pn(u, v) for the probability that a random walk started at the vertexu of the graph is at the vertex v at time n.11.2. Random walks on graphsPerhaps the first important work in the tradition we describe was George Po´lya’s 1921 paper[196], in which he proved the following theorem. We say that a graph is recurrent if the randomwalk on the graph returns to its starting location almost surely (i.e., with probability one – we willhenceforth abbreviate this to a.s.), and transient if it has a positive probability never to return. Itis easy to see that the graph is recurrent if and only if the random walk returns to its starting pointinfinitely many times a.s., and transient if and only if it returns to its starting point only finitelymany times a.s. The hypercubic lattice Zd is the graph whose vertices are d-tuples of integers,and where two vertices are connected by an edge if they differ by exactly one in one coordinate andhave the same value in all other coordinates.Theorem (Po´lya 1921). The d-dimensional hypercubic lattice Zd is recurrent if d ≤ 2, and transientif d ≥ 3.This theorem can be summarised by the following famous aphorism, attributed to Shizuo Kaku-tani.A drunk man will find his way home,but a drunk bird may get lost forever.Po´lya’s proof of his theorem was computational in nature. By computing the moment generatingfunction of the location of the random walk at time n, Po´lya showed that the random walk on Zdsatisfiesp2n(0, 0) ≈ n−d/2. (1.2.1)On the other hand, it is easy to see that, for parity reasons, pn(0, 0) = 0 for every odd n. Thisestimate easily yields the theorem, since it is not hard to prove that the random walk on a graphis recurrent if and only if ∑n≥1pn(v, v) =∞for some (and hence every) vertex v of G – note that this sum is exactly the expected number oftimes the walk returns to v.A drawback to this approach is that it relies heavily upon the symmetries of the lattice, and isnot very robust. For example, the argument breaks down rather seriously if we take some arbitraryset of edges of Zd and replace each of the edges in this set with two edges in parallel with thesame endpoints. Besides this, it does not give us much insight into the geometric reasons that Z2is recurrent but Z3 is transient.1.2.1 The Nash-Williams Criterion and electrical networksThe first major step towards a geometric understanding of the recurrence/transience problem wasthe Nash-Williams Criterion [186], which gives a sufficient condition for recurrence in terms ofthe isoperimetry of the graph. For each set of vertices W ⊆ V in a graph G, we write |W | =∑v∈W deg(v). We say that a set W is a cutset for v if every path from v to infinity must passthrough W .21.2. Random walks on graphsTheorem (Nash-Williams 1959). Let G be an infinite graph, let v be a vertex of G, and supposethat there exists a disjoint sequence of finite cutsets Wi for v such that∑i≥1|Wi|−1 =∞.Then G is recurrent.This theorem easily recovers Po´lya’s result in dimensions 1 and 2 by, for example, using thecutsets Wi = {−i, i} in Z and the cutsets Wi = {(x, y) : |x|+ |y| = i} in Z2.Nash-Williams’s proof was based on the correspondence between random walks and electricalnetworks, a tool which will be of great importance throughout this thesis. A detailed introduction,covering everything we discuss in this subsection, can be found in [173, Chapters 2 and 3]. We canthink of a graph as an electrical network in which each edge contains a unit resistor1. Supposethat we have such a network arising from a finite graph, and we attach the two ends of a batteryto two disjoint sets of vertices, A and B. Doing this will cause a current to flow through thenetwork. Mathematically, the current flow is a function θ from the set of oriented edges ofthe graph (that is, edges e together with a choice of one of the endpoints as the tail of the edge,denoted e−, and the other as the head of the edge, denoted e+) that is antisymmetric in the sensethat θ(e) = −θ(−e) for every oriented edge e of G, where −e denotes the reversal of e. Given anantisymmetric edge function θ and a vertex v, we write ∇∗θ(v) for the sum ∑e−=v θ(e).Kirchoff’s laws of electrical networks [154] are as follows:1. (The node law) For every vertex v of G, the sum ∇∗θ(v) of the currents along the orientededges emanating from v is positive if v ∈ A, negative if v ∈ B, and zero if v is not in A or B.2. (The cycle law) If e1, e2, . . . , en form a cycle, a path from A to itself, or a path from B toitself, then∑ni=1 θ(ei) = 0.In general, we call an antisymmetric edge function satisfying the node law a flow from A toB. It is not hard to prove that, in a finite network, the antisymmetry condition and Kirchoff’slaws determine the current flow up to a positive multiplicative constant. The strength of a flow isdefined to be the sum∑v∈A∇∗θ(v), and we say that a flow is a unit flow if it has strength one.We define the unit current flow from A to B to be the unique current flow from A to B that hasstrength 1.Given a function f : V → R, we define the gradient ∇f to be the antisymmetric edge function∇f(e) = f(e+)− f(e−).1We can also consider networks with arbitrary resistances, for which there is a corresponding random walk thatchooses which edge to travel along weighted by its conductance, that is, the inverse of its resistance.31.2. Random walks on graphsThe basic connection between electrical network theory and random walks is that voltages (i.e.,antiderivatives of currents) are hitting probabilities. Given a graph G, we write Pv for the law ofthe random walk started at v. For each set of vertices A, we write τA for the first time that therandom walk hits A.Proposition. Let f(v) = Pv(τB < τA). Then the gradient ∇f is a current flow from A to B.This is all well and good, but so far the electrical theory has not given us a useful way ofcalculating anything. However, the theory becomes very useful once we introduce effective resis-tances. The energy of an antisymmetric edge function θ, and the Dirichlet energy of a functionf : V → R, are defined byE(θ) = 12∑e∈E→θ(e)2 and E(f) = 12∑e∈E→(f(e+)− f(e−))2= E(∇f).The effective resistance between two disjoint sets A and B in a finite graph is defined to be theenergy of the unit current flow from A to B, and is denoted Reff(A ↔ B) (or Reff(A ↔ B;G) ifthe graph we are considering is not clear). Effective resistances are related to hitting probabilitiesas follows. Write τ+A for the first time that the random walk hits A after time zero.Proposition. Reff(A↔ B)−1 =∑v∈A deg(v)Pv(τB < τ+A ).In particular, the reciprocal of the effective resistance (a.k.a. the effective conductance)between a single vertex a and a set B is exactly the multiple of deg(a) with the probability thatthe random walk started at a hits B before it returns to a.The reason this is so useful is that we have the following two variational principles for theeffective resistance.Theorem (Thomson’s Principle).Reff(A↔ B) = inf{E(θ) : θ is a flow from A to B with strength at least one}.Theorem (Dirichlet’s Principle).Reff(A↔ B)−1 =inf{E(f) : f : V → R such that f(v) ≤ 0 for all v ∈ A and f(v) ≥ 1 for all v ∈ B}.These allow us to get an upper bound on the effective resistance by constructing a low energyflow, or to get lower bounds by exhibiting low energy functions. (There are also several other closelyrelated variational formulas for the effective resistance - the key words are extremal length andthe method of random paths.)Exercise. Prove both Thomson’s and Dirichlet’s principles. Hint: Differentiate the energy withrespect to θ or f as appropriate and find the critical points.41.2. Random walks on graphsNow suppose that G is an infinite graph and A is a finite set of vertices in G, and let 〈Vn〉n≥0be an exhaustion of G, that is, an increasing sequence of finite sets of vertices such that⋃n≥0 Vn.We define ∂V Vn to be the set of vertices of Vn that have a neighbour not in Vn, and let Gn be thesubgraph of G induced by Vn, that is, the graph that has vertex set Vn and has all the edges of Gthat have both endpoints in Vn. We defineReff(A→∞) = limn→∞Reff(A→ ∂Vn;Gn),so thatReff(A→∞)−1 = limn→∞∑v∈Adeg(v)Pv(τ∂Vn < τ+A ) =∑v∈Adeg(v)Pv(τ+A =∞).Thus, we have that a graph is recurrent if and only if the effective resistance from some (andhence every) vertex to infinity is infinite. Both Thomson’s and Dirichlet’s principles extend toyield variational formulas for the effective conductance to infinity, with appropriate modifications:a flow from A to infinity is required to have ∇∗θ(v) positive if v ∈ A and zero otherwise, while inthe Dirichlet principle we can take the infima over functions that are finitely supported (i.e. havef(v) = 0 for all but finitely many vertices v) and have f(v) ≥ 1 for all v ∈ A.An important consequence of Thomson’s principle is that the effective resistance is a monotonefunction of the edge set, a fact known as Rayleigh’s monotonicity principle. In particular, thisimplies that every subgraph of a recurrent graph is recurrent. This is not obvious at all by directconsideration of the random walk.We are now ready to see how the Nash-Williams Criterion is proven. For each of the cutsetsWi, let Vi be the set of vertices u such that Wi is a cutset for u, and, for each n ≥ 1, define afinitely supported function fn with fn(v) = 1 byfn(u) =∑ni=1 |Wi|−11(u ∈ Vi)∑ni=1 |Wi|−1.Since the gradients ∇1(u ∈ Vi) have disjoint support, we can compute thatE(fn) =∑ni=1 |∂EVi| · |Wi|−2(∑ni=1 |Wi|−1)2 ≤ n∑i=1|Wi|−1−1 .Thus, we haveReff(v →∞) ≥ E(fn)−1 ≥n∑i=1|Wi|−1,and the claim follows since n was arbitrary.Exercise. Prove that Zd is transient for d ≥ 3 by exhibiting a flow from the origin to infinity thathas finite energy.51.2. Random walks on graphsFigure 1.1: Z2, left, is amenable, while the 3-regular tree, right, is nonamenable.1.2.2 The isoperimetric approachThe next milestone result in the theory was proven by Kesten, also in 1959. Nash-Williams gives usa good geometric criterion for recurrence, but what about transience? One rather extreme way fora graph to be transient, which turns out to have a simple geometric description, is for the returnprobabilities pn(v, v) to decay exponentially in n, meaning that there exists a constant α < 1 andconstants Cv <∞ such thatpn(v, v) ≤ Cvαnfor every v ∈ V and n ≥ 0.Kesten’s theorem [151, 152] relates exponential decay of the return probabilities to the isoperime-try of the graph, that is, to the relationship between the sizes of sets in the graph to the sizes oftheir boundaries. We write |∂W | for the number of edges that have one endpoint in W and theother outside of W . A graph is said to be nonamenable if there exists a positive constant c > 0such that |∂W |/|W | > c for every finite set W ⊂ V , and amenable otherwise. For example, Zd isamenable for every d ≥ 1 because∣∣∣[0, n]d∣∣∣ = nd but ∣∣∣∂[0, n]d∣∣∣ ≈ nd−1,so that |∂[0, n]d|/|[0, n]d| → 0 as n → ∞. On the other hand, the d-regular tree2 is nonamenablefor every d ≥ 3: The average degree of a vertex in a finite tree with n vertices is easily seen to be2− 2/n ≤ 2, and it follows by an elementary calculation that for any finite subset W of a d-regulartree, we have|∂W | ≥ (d− 2)|W |.Theorem (Kesten 1959). Let G be a graph, and let v be a vertex of G. Then pn(v, v) decaysexponentially if and only if G is nonamenable.2A forest is a graph that does not contain any simple cycles. A tree is a connected forest. The d-regular tree isthe unique tree in which every vertex has degree d.61.2. Random walks on graphsKesten proved his theorem only for random walks on groups. The generalisation to arbitrarygraphs, as well as quantitative forms of the theorem, are due to many authors working in variouscontexts [11, 53, 65, 68, 80, 81, 101, 143, 224]. See [173, Chapter 6.10] for a detailed history. Thefact that the exponential decay of the return probabilities implies nonamenability is rather easy,the difficult part is the other direction.Nonamenability has many guises, and the amenability/nonamenability dichotomy is fundamen-tal not only to the study of random walks, but also of percolation, uniform spanning forests, andmany other topics that we will not touch on here, such as the ergodic theory of group actions.Indeed, the Wikipedia page on amenable groups lists nine different properties of groups that areequivalent to amenability.We might hope for a nice isoperimetric criterion for transience, along the lines of Kesten’sTheorem and the Nash-Williams Criterion, which also has an isoperimetric character. Note thatattaching an infinite path to a graph will not affect whether or not the graph is transient, but willcause the graph to have very bad isoperimetry, suggesting that the best we can hope for in generalis a sufficient condition for transience in terms of isoperimetry.We say that a graph G satisfies an φ(t)-isoperimetric inequality if there exists a positiveconstant c > 0 such that |∂W |/φ(|W |) > c for every finite set W ⊂ V . In particular, G isnonamenable if and only if it satisfies a t-isoperimetric inequality. Similarly, we say that G satisfiesan anchored φ(t)-isoperimetric inequality if there exists a positive constant c > 0 such that|∂W |/φ(|W |) > c for every finite connected set W ⊂ V containing some fixed vertex v (the choiceof which does not matter). The following theorem was proven by Thomassen [220]. The versionwe state here appears in the textbook of Lyons and Peres [173], and is adapted from a theorem ofLyons, Morris, and Schramm [170]. Similar theorems have also been obtained by He and Schramm[121], and Benjamini and Kozma [42].Theorem (Thomassen’s Criterion). Suppose that G satisfies an anchored φ(t)-isoperimetric in-equality for some increasing function φ such that∞∑n=1φ(n)−2 <∞.Then G is transient.What if we are interested in the rate of decay of pn(u, u) (known in the jargon of the field as theon-diagonal heat kernel), rather than just the transience/recurrence question? In particular,is there a geometric proof of Po´lya’s estimate (1.2.1)? For d ≥ 2 an answer is provided by thefollowing results. We say that a graph satisfies a d-dimensional isoperimetric inequality if it satisfiesa t(d−1)/d-isoperimetric inequality. Zd satisfies a d-dimensional isoperimetric inequality, so that wecan recover Po´lya’s estimate from the following two theorems: See the textbooks [229] and [159]for history, proofs, and related theorems.71.2. Random walks on graphsTheorem. Let G be an infinite, bounded degree graph and let d ≥ 2. Then G satisfies a d-dimensional isoperimetric inequality if and only if there exists a constant C <∞ such thatpn(u, u) ≤ C n−d/2for every vertex u and n ≥ 1.Theorem. Let G be an infinite, bounded degree graph that satisfies a d-dimensional isoperimetricinequality for some d ≥ 2, and suppose that there exists a constant C <∞ such that|B(u, r)| ≤ C rdfor every vertex u and every r ≥ 1. Then there exists a constant c > 0 such thatpn(u, u) ≥ cn−d/2for every vertex u and every n ≥ 1.It is possible to say much more. In particular, it is possible to recover the entire (off-diagonal)behaviour of the heat kernel pn(x, y) on Zd from geometric considerations. This understandinghas proven very important for developing a similar understanding for random walk on fractal-likegraphs such as the (pre-)Sierpinski gasket.1.2.3 Bounded harmonic functionsRecall that a function h on a graph is said to be harmonic if for each vertex u, the value of hat u is equal to the average value of h on the neighbours of u. The existence or nonexistence ofvarious types of non-constant harmonic functions (e.g. bounded, finite energy, positive, polynomialgrowth) on a graph is closely connected to the behaviour of the random walk on the graph.Perhaps the most important class of harmonic functions are the bounded harmonic functions.In probabilistic terms, bounded harmonic functions encode all possible ‘behaviours at infinity’ ofthe random walk that occur with positive probability. The correspondence, which goes back to thework of Blackwell [55], can be stated (more or less) precisely as follows: First, suppose we have a(measurable) set A of paths in G that is shift invariant in the sense that if we delete an initialsegment of any path in A , then the truncated path is also in A . We can define a function h on Gby setting h(v) to be the probability that if we start a random walk at v, then the resulting pathwill be in the set A . It is not hard to verify that, since A is shift invariant, the function h(v) isharmonic.More generally, we can obtain a bounded harmonic function on G from any (measurable)bounded shift invariant function on the set of paths in G, by taking the expectation of the functionapplied to the random walk. In fact, the function needs only be defined on some set that the ran-dom walk path is a.s. in, and two shift invariant functions will yield the same harmonic function if81.2. Random walks on graphsand only if they yield the same value on a.e. random walk path. It can be shown that in fact everybounded harmonic function on G arises this way. In particular, G admits non-constant boundedharmonic functions if and only if there is some shift-invariant set of paths A and a vertex v suchthat the probability that the random walk started at v is in the set A is strictly between 0 and 1(that is, if the invariant σ-algebra is nontrivial). We say that a graph is Liouville if it does notadmit any non-constant bounded harmonic functions, and non-Liouville otherwise. See [173] fora detailed treatment of the theory of bounded harmonic functions and the Liouville property.For example, it can be shown that Zd is Liouville for every d ≥ 1 (see below). On the otherhand, if we attach together two copies of Z3 (with vertex sets {1} × Z3 and {2} × Z3) by a singleedge connecting their origins, then the resulting graph is non-Liouville, and in fact the vector spaceof bounded harmonic functions on this graph is equal to the linear span of the constant 1 functionand the functionh(x) = P(a random walk 〈Xn〉n≥0 started at v visits the set {1} × Z3 infinitely often).In other words, which of the two copies of Z3 the random walk is eventually absorbed into is theonly non-trivial information there is about the random walk on this graph.How can we tell if a graph is Liouville or not? For transitive graphs, there is a nice char-acterisation, which follows in the special case of Cayley graphs from the work of Avez [26, 27],Derriennic [77], and Kaimanovich and Vershik [149, 226], and was generalised to transitive graphsby Kaimanovich and Woess [148]. Here, an automorphism of a (simple) graph G is a bijectionφ : V → V such that φ(u) is adjacent to φ(v) if and only if u is adjacent to v, and a graph G istransitive if for every two vertices u and v of G, there is an automorphism of G sending u to v.Intuitively, a graph is transitive if it ‘looks the same from every vertex’.Theorem. Let G be a transitive graph. Then the following are equivalent.1. The random walk on G has positive speed, meaning thatlim infn→∞1nd(X0, Xn) > 0almost surely when 〈Xn〉n≥0 is a random walk on G.2. The asymptotic entropylim infn→∞1n∑v∈V−pn(u, v) log pn(u, v) = lim infn→∞1nEu[− log pn(X0, Xn)]is positive for every vertex u of G.3. G is non-Liouville.91.2. Random walks on graphs(In fact the limits infimum here can be replaced with limits: This follows from Kingman’s sub-additive ergodic theorem for the speed, and Fekete’s Lemma for the asymptotic entropy.) This the-orem allows us to immediately conclude that every transitive nonamenable graph is non-Liouville,since Kesten’s theorem easily implies that both the speed and asymptotic entropy are positive forany bounded degree nonamenable graph. On the other hand, the theorem also implies that everytransitive graph that has subexponential growth, meaning thatlim infn→∞1nlog |B(u, n)| = 0is Liouville, since an easy computation implies that∑v∈V−pn(u, v) log pn(u, v) ≤ log |B(u, n)|for every vertex u and n ≥ 0. Both of these conclusions fail for general bounded degree graphs.Unfortunately, there is still no good geometric understanding of the Liouville property, partic-ularly for the interesting case of amenable transitive graphs of exponential growth, some of whichare Liouville and some of which are not. In particular, it is a long-standing open problem to provethe widely believed claim that two Cayley graphs of the same group are either both Liouville orboth non-Liouville.The fact that item (1) implies item (2) in the previous theorem is a corollary of the Varopoulos-Carne inequality [66, 225], which is a beautiful theorem in its own right. (Its proof, due to Carne,is an extremely elegant piece of linear algebra involving an expansion of the n-step transition matrixPn in terms of Chebyshev polynomials of P ).Theorem (Varopoulos-Carne). Let G be a graph. Thenpn(u, v) ≤ 2√deg(v)/ deg(u) exp(−d(u, v)2/(2n)).Exercise. Use the Varopoulos-Carne Inequality to prove that the positivity of the speed and ofthe asymptotic entropy are equivalent for any bounded degree graph.A further nice consequence of the Varopoulos-Carne bound is that for any graph G which haspolynomial growth, meaning that there exist constants C, d <∞ such that|B(u, n)| ≤ C ndfor every vertex u and every n ≥ 0, we have thatlim supn→∞d(X0, Xn)√n log(n)<∞almost surely, so that graphs with polynomial growth are quite far away from having positive speed.101.2. Random walks on graphsExercise. Prove this claim.1.2.4 The Poisson boundaryIf we have a graph that we know to be non-Liouville, it is interesting to classify the space of allbounded harmonic functions in some geometric way. See [173, Chapter 14] for a detailed treatmentof the material covered in this subsection.The model situation is the classical Poisson integral formula, which states that for every boundedharmonic function u on the unit disc D, there exists a bounded measurable function f on ∂D (uniqueup to almost-everywhere equivalence) such thatu(z) =12pi∫ 2pi01− |z|2∣∣z − eiθ∣∣2 f(eiθ) dθ, (1.2.2)and moreover that any function u on D defined in this way is bounded and harmonic. The equation(1.2.2) therefore yields an isomorphism between the Banach spaces of bounded harmonic functionson the unit disc and bounded measurable functions on the unit circle, both with the uniform norm.Moreover, the right hand side of the expression is equal to the expectation of f(BT ), where B isBrownian motion started at z, and T is the first time B hits ∂D.This example led Furstenberg, in his pioneering works [91–93], to define the notion of a Poissonboundary of a graph in the discrete setting. A compactification G of a graph G is a compact,metrisable topological space containing the vertex set of G as a dense, discrete subset. Given acompactification G, we write ∂G = G \ V . We say that the (boundary of the) compactification isa Poisson boundary of a transient graph G if the random walk on G converges in the compacti-fication a.s., and, for every bounded harmonic function h on G, there exists a bounded measurablefunction (unique up to almost everywhere equivalence) f : ∂G→ R such thath(v) = Ev f(limn→∞Xn)for every vertex v. (Note that the limit point of the walk is a shift invariant function of the walk,so that if we start with a bounded function f on the boundary then the function h defined as aboveis certainly bounded and harmonic.) For example, the one-point compactification is a Poissonboundary of a transient graph G if and only if G is Liouville. Probabilistically, a compactificationG of G is a Poisson boundary of G if the limit of a random walk in the compactification encapsulatesall of the walk’s limiting behaviour.Although we have defined it topologically, the Poisson boundary is really a measure-theoreticnotion, and two compactification Poisson boundaries of the same graph need not be homeomorphic(this is in contrast to the Martin boundary, defined in terms of positive harmonic functions, whichis truly a topological object, see e.g. [201]).111.2. Random walks on graphsFor example, suppose that we have a transient tree. An end of the tree is an equivalenceclass of rays (i.e. infinite simple paths) in the tree, where two rays are equivalent if they have finitesymmetric difference. The ends compactification of the tree is a compact topological space whosepoints are the vertices and ends of the tree, and where a sequence of vertices 〈vi〉i≥0 converges toan end ξ if, fixing some root vertex ρ of the tree arbitrarily, the geodesics in the tree connectingρ to vi converge to a ray in the equivalence class of the end ξ. In particular, a path converges toan end in the ends compactification of a tree if and only if the path is transient, i.e. visits eachvertex of the tree at most finitely often, and so the random walk on a tree converges a.s. in theends compactification if and only if the tree is transient. Now, if a function converges along atransient path, in a tree, it must also converge along any ray corresponding to the end that thatpath converges to. If h is a bounded harmonic function on a transient tree and X is a randomwalk started at ρ, then, by the Martingale convergence theorem, the limit of h along X exists a.s.,and it follows that h converges a.s. along the ray starting at ρ that corresponds to the end that Xconverges to. This allows us to define a bounded function f on the boundary byf(ξ) = limn→∞h(vi)where 〈vi〉i≥0 is a ray corresponding to the end ξ. We clearly have thath(v) = Ev f(limn→∞Xn),so that the ends compactification is a Poisson boundary of any transient tree.In general, it is not hard to show that a compactification Poisson boundary exists for anytransient graph. For example, the Martin boundary is also a Poisson boundary (but easier con-structions also exist). However, giving a geometric construction of the Poisson boundary, or showingthat some particular compactification is indeed a Poisson boundary, can be highly non-trivial. Inthe next section, we shall see that for bounded degree triangulations, there is a beautiful geometricconstruction of the Poisson boundary using circle packing.1.2.5 Infinite electrical networks and harmonic Dirichlet functionsIn Section 1.2.1, we saw how to define the effective resistance between two sets in a finite graph,and also the effective resistance from a finite set to infinity in an infinite graph. What about theeffective resistance between two finite sets in an infinite graph? It turns out that there is more thanone reasonable way to define this, leading to different quantities that have different significance,since unit currents in the graph might no longer be unique. See [173, Chapter 9] for a detailedtreatment of the material covered in this subsection.Perhaps the most obvious way to define effective resistances in an infinite graph is to use anexhaustion by induced subgraphs as we did before. This yields the free effective resistance. LetG be an infinite graph, let 〈Vn〉n≥1 be an exhaustion of G, and let Gn be the subgraph of G induced121.2. Random walks on graphsFigure 1.2: Free (left) and wired (right) boundary conditions on a 6× 6 square in Z2.by Vn for each n ≥ 1. The free effective resistance between two finite sets A and B in G is definedto beRFeff(A↔ B;G) = limn→∞Reff(A↔ B;Gn).Exercise. Prove that this limit exists and does not depend on the choice of exhaustion.We call an antisymmetric edge function on an infinite graphG a current if it satisfies Kirchhoff’snode and cycle laws, and has finite energy. It turns out that the unit current flows from A to B inthe graphs Gn also converge to a current in G, called the free unit current flow from A to B,whose energy is exactly the free effective resistance.Free effective resistances also obey a version of the Thomson and Dirichlet principles:RFeff(A↔ B) =inf{E(θ) : θ is a finitely supported flow from A to B with strength at least one}andRFeff(A↔ B)−1 =inf{E(f) : f : V → R is a function with f(v) ≥ 1 for all v ∈ A and f(v) ≤ 0 for all v ∈ B}.What if we instead take the infimal energy over all flows, not just those that are finitelysupported? This leads to the wired effective resistance, defined byRWeff (A↔ B) = inf{E(θ) : θ is a flow from A to B with strength at least one}.In fact, it can be shown that this infimum is a minimum, that there is a unique flow obtaining thisminimum, and that this flow is a unit current flow from A to B, called the wired unit currentflow from A to B.Wired effective resistances and currents can also be obtained from an exhaustion as follows. Let〈Vn〉n≥0 be an exhaustion of an infinite graph G. For each n, we also construct a graph G∗n from131.3. Circle packingG by gluing (wiring) every vertex of G \ Vn into a single vertex, denoted ∂n, and deleting all theself-loops that are created. We identify the set of edges of G∗n with the set of edges of G that haveat least one endpoint in Vn. Then we haveRWeff (A↔ B) = limn→∞Reff(A↔ B;G∗n),and the unit current flow from A to B in G∗n converges to the wired unit current flow from A to B.When are the free and wired effective resistances between any two sets the same? We say thata graph has unique currents if for any two finite sets A and B, there is a unique unit currentflow from A to B.Proposition. Let G be an infinite graph. Then the wired and free effective resistances between anytwo sets are equal if and only if G has unique currents, if and only if G does not admit non-constantharmonic functions of finite Dirichlet energy.This proposition tells us to expect non-constant harmonic functions of finite Dirichlet energyto play an important role in the electrical theory of infinite graphs. When do such functions exist?Proposition. Let G be an infinite graph. If G admits non-constant harmonic functions of finiteDirichlet energy, then G admits non-constant bounded harmonic functions of finite Dirichlet energy.In particular, G is non-Liouville.Proposition. Let G be an amenable transitive graph. Then G does not admit harmonic functionsof finite Dirichlet energy.It is more subtle to determine whether or not a nonamenable transitive graph admits non-constant harmonic functions of finite Dirichlet energy. (For Cayley graphs of groups, it is equivalentto the positivity of the first `2-Betti number of the group, see [173, Chapter 8.10].) Surprisingly, itis not monotone in how ‘large’ or ‘expansive’ the graph is. For example, if G is a bounded degreegraph rough isometric to d-dimensional hyperbolic space, then G admits non-constant harmonicDirichlet functions if and only if d = 2. Moreover, if G1 and G2 are any two infinite graphs, thenthe direct product of G1 and G2 does not admit any non-constant harmonic Dirichlet functions.1.3 Circle packing1.3.1 Planar graphs and mapsA planar graph is a graph that can be drawn in the plane so that no two edges intersect. Given agraph, a proper embedding of the graph into an oriented surface S is a drawing of the graph inthe surface such that each compact set in the domain intersects at most finitely many edges of thegraph, and each face of the drawing (i.e. connected component of the complement of the drawing)is homeomorphic to a disc. (For embeddings with infinite faces in multiply-connected surfacesthere is an additional technical condition required of proper embeddings which will not concern141.3. Circle packingFigure 1.3: Different maps with the same underlying graph. A map is determined by a graphtogether with a cyclic ordering of the oriented edges emanating from each vertex.us here.) A map is a graph together with an equivalence class of proper embeddings, where twoproper embeddings are considered equivalent if there is an orientation preserving homeomorphismmapping one surface to the other that sends one embedding to the other. The map is planar ifthe surface can be taken to be a domain D ⊂ C ∪ {∞}, and is simply connected if the surfacecan be taken to be the plane (or, equivalently, the open disc). Thus, a graph is planar if and onlyif it is the underlying graph of some planar map.It turns out (see [184]) that maps can be described combinatorially as graphs together withcyclic permutations {σv : v ∈ V } of the oriented edges emanating from each vertex, which specifythe clockwise order of these edges in an embedding, so one does not need to be a topologist tostudy them.The dual of a map is the map M † that has the faces of M as vertices, the vertices of M asfaces, and for each edge e of M has an edge e† connecting the faces of M that are on either side ofe. We say that a map has bounded codegrees if its faces have a bounded number of sides, or,equivalently, if its dual has bounded degrees.Figure 1.4: A finite planar map (black, solid) and its dual (red, dashed).1.3.2 Circle packingThere are many ways to draw a planar map, which may or may not be useful for analyzing thebehaviour of random walk and other processes on the graph. One of the best ways is given bythe circle packing theorem. This theorem yields a canonical method of drawing planar graphs,closely connected to conformal mapping, and endows the graph with a geometry that, for many151.3. Circle packingpurposes, is better than the usual graph metric. Indeed, for bounded degree triangulations, acomprehensive theory has been developed by Angel, Barlow, Gurel-Gurevich, and Nachmias [17],and Chelkak [69], showing that the random walk on the circle packing behaves very similarly to aquasiconformal image of standard planar Brownian motion: Effective resistances, heat kernels, andharmonic measures on the graph can each be estimated in terms of the corresponding Brownianquantities. See [202] and [215] for introductions to the theory of circle packing. The interestedreader may also enjoy making their own circle packings using Ken Stephenson’s CirclePack software[214].In this section, we will review the main theorems of circle packing as they relate to randomwalks and potential theory. Later, we will apply this theory to study uniform spanning forests ofplanar graphs, and will also study circle packings of unimodular random triangulations, two of themajor topics of original research in this thesis. Moreover, we will develop the dichotomy betweenparabolic and hyperbolic bounded degree planar maps, which will motivate the development of asimilar dichotomy for unimodular random planar maps, a further major topic of original work inthis thesis.A circle packing of a planar map G is a set of discs P = {P (v) : v ∈ V } with disjoint interiorsin the Riemann sphere C ∪ {∞}, one for each vertex of G, such that two discs are tangent if andonly if their corresponding vertices are adjacent in G. The existence and uniqueness theorem forcircle packings, or simply the Circle Packing Theorem, is in our opinion one of the most beautifulresults in all of mathematics. It was first discovered by Koebe in 1936 [156] as a corollary to hiswork on the Riemann mapping theorem for multiply connected domains, but went largely forgottenuntil Thurston [221] (who was unaware of Koebe’s proof) rediscovered it as a corollary to the workof Andreev [14] on convex polyehdra. Due to this storied history, the Circle Packing Theorem isoften called the Koebe-Andreev-Thurston Theorem. Like graphs, maps are said to be simple ifthey do not have any loops or multiple edges.Theorem. Every finite, simple planar map has a circle packing in the Riemann sphere. If the mapis a triangulation, then its circle packing is unique up to Mo¨bius transformations.The circle packing theorem was extended to infinite, simple, simply connected triangulationsby He and Schramm [121, 122]. Their theorem can be thought of as a discrete analogue of theUniformization Theorem for Riemann Surfaces. (Indeed, a celebrated theorem of Rodin and Sulli-van [200] states that circle packings can be used to approximate conformal maps.) The carrier ofthe circle packing of a triangulation is the union of the discs in the triangulation together with thecurved triangular regions surrounded by three circles that correspond to the triangles of the map.A circle packing is said to be in a domain D ⊆ C ∪ {∞} if its carrier is D.Theorem (Schramm 1991, He and Schramm 1993). Let T be an infinite, simple, simply connectedtriangulation. Then T admits a circle packing either in the plane or in the disc, but not both, andthis circle packing is unique up to Mo¨bius transformations of the plane or the disc as appropriate.161.3. Circle packingFigure 1.5: Circle packings of the 6-regular and 7-regular triangulations.In light of this theorem, we call a simply connected triangulation CP parabolic if it can becircle packed in the plane, and CP hyperbolic otherwise. A rather trivial compactness argument(using the Ring Lemma, below) shows that every simple triangulation can be circle packed in somedomain D ⊆ C ∪ {∞}. It is much harder to show that we can circle pack inside a domain that isgeometrically nice. (In fact, He and Schramm proved that, in the CP hyperbolic case, we can circlepack in any simply connected domain D strictly contained in the plane.)Recall that the unit disc can be identified with the hyperbolic plane through the Poincare´ discmodel, and that, under this identification, circles in the unit disc and circles in the hyperbolicplane are the same, but have different centres and radii. Moreover, the Mo¨bius transformationsof the disc are exactly the orientation-preserving isometries of the hyperbolic plane. Thus, theabove theorem tells us to expect a strong connection between CP hyperbolic triangulations andhyperbolic geometry.He and Schramm [121] also pioneered the application of circle packing to probabilistic problems,proving the following remarkable theorem.Theorem (He and Schramm 1995). Let T be an infinite, simple, bounded degree, proper planetriangulation. Then T is CP parabolic if and only if it is recurrent.The He-Schramm Type Theorem follows as an immediate consequence of the following estimate,which also gives a good flavour of the kind of analysis we can do with circle packings. Let us firstintroduce some notation. Given a triangulation T and a circle packing P of T , we write z(v)and r(v) for the (Euclidean) centre and radius, respectively, of the disc P (v). Given z ∈ C andR ≥ r > 0, we write Bz(r) for the ball {w ∈ C : |w − z| ≤ r}, and Az(r,R) for the annulus{w ∈ C : r ≤ |w − z| ≤ R}.171.3. Circle packingLemma (Resistances across annuli). Let T be a plane triangulation, and let P be a circle packingof T in some domain D ⊆ C ∪ {∞}.1. (Upper bound.) There exists a universal constant C such that the following holds. For everyclosed annulus Az0(r, αr) ⊂ D with α ≥ 2 such that {v : z(v) ∈ Bz0(r)} 6= ∅, we haveReff({v : z(v) ∈ Bz0(r)}↔ {v : z(v) ∈ D \Bz0(α r)}) ≤ C logα.2. (Lower bound.) Suppose that T has bounded degrees. Then there exists a constant C ′ dependingon the maximal degree of T such that the following holds. For every closed annulus Az0(r, αr)with α ≥ 2 (not necessarily contained in D) such that {v : P (v) ⊆ Bz0(r)} 6= ∅, we haveRFeff({v : P (v) ⊆ Bz0(r)}↔ {v : z(v) ∈ D \Bz0(α r)}) ≥ C ′ logα.The idea is that we can use the geometry of the circle packing to define a flow of sufficientlylow energy (to obtain the upper bound via Thomson’s principle), and functions of sufficiently lowenergy (to obtain the lower bound via the Dirichlet principle).For the upper bound, we can define a flow that dissipates radially outwards in a roughly sym-metric fashion. (This is best done with the method of random paths, defining a random path bytaking the path in the graph that interpolates a radial line segment at a uniformly random anglefrom the centre of the annulus.)For the lower bound, the Ring Lemma of Rodin and Sullivan [200] is a crucial ingredient, whichgives us geometric control of the circle packing if we can control the degrees of vertices in thetriangulation (for instance, in the bounded degree case).Theorem (The Ring Lemma; Rodin and Sullivan 1987). There exists a sequence of constants〈kn : n ≥ 3〉 such that the following holds. If P is a circle packing of a planar triangulation in somedomain D ⊆ C ∪ {∞}, and v is a vertex of G such that P (v) does not contain ∞, thenr(v)/r(u) ≤ kdeg(v)for every vertex u adjacent to v.In the setting of item 2. of the resistances across annuli lemma, the Ring Lemma implies thatthere exists some constant β > 2 depending on the maximal degree such that if Bz0(r) contains acircle then the set of circles intersected by each of the annuli Az0(βnr, 2βnr) and Az0(βn+1r, 2βn+1r)are disjoint for every n. This allows us to reduce to the case α = 2, since we can then add upthe resistances across each of the logβ(α) many annuli Az0(βnr, 2βnr) by the series law. The caseα = 2 can then be handled by normalizing so that z = 0 and r = 1/2, and then using the function|z| in Dirichlet’s principle to obtain a lower bound on the free effective resistance.181.3. Circle packingThis resistance estimate has many further uses. For example, it can be used to prove our nextmilestone theorem about circle packing, the Benjamini-Schramm Convergence Theorem [47].Theorem (Benjamini and Schramm 1996). Let T be a CP hyperbolic, simply connected, boundeddegree triangulation, and let P be a circle packing of T in the disc. Then the random walk on Tconverges to a point in the boundary of the disc almost surely, and the law of the limit point hasfull support and no atoms.Here, ‘the law of the limit point has full support’ means that every interval in the boundary ofpositive length has a positive probability to contain the limit point of the random walk, while ‘thelaw of the limit point has no atoms’ means that for any particular point in the boundary, the limitof the walk does not equal that point a.s.In fact, there is an easy proof of the convergence and nonatomicity parts of this theorem usingthe resistances across annuli lemma above, first observed in the author’s work with Yuval Peres[132], which we now sketch. If v is a vertex and A is a set of vertices in a transient graph G, thenwe have the estimatePv(τA <∞) ≤ Reff(v →∞)RFeff(v ↔ A).Suppose we have a bounded degree triangulation circle packed in the disc, and that v is a fixedvertex of the triangulation. Then we have that there is some constant C <∞ such thatPv(the random walk started at v ever hits {v : P (v) ⊆ Bξ(ε)}) ≤ C log(1/ε)−1for all ξ ∈ ∂D and all ε sufficiently small. In particular, for each point ξ ∈ ∂D, we havePv(ξ is in the closure of the set {z(Xn) : n ≥ 0})= 0. (1.3.1)We can now deduce convergence and nonatomicity: Observe that, for topological reasons, theintersection of ∂D with the closure of the set {z(Xn) : n ≥ 0} is an interval a.s. (The key pointpowering this is that |z(Xn)| → 1 and r(Xn) → 0 a.s. as n → ∞ by transience.) The estimate(1.3.1) implies that the expected length of this interval is zero, and so the interval must be a pointa.s., establishing convergence. The fact that the law of the limit point does not have any atoms isobvious from (1.3.1).An immediate consequence of the Benjamini-Schramm convergence theorem is that every tran-sient, bounded degree, simple, proper plane triangulation is non-Liouville: For any bounded, mea-surable function f : ∂D→ V , we can define a harmonic function on T byh(v) = Ev f(limn→∞ z(Xn)),and this function will be non-constant provided that f is not (almost everywhere) constant. Infact, it is not too hard to reduce the case of a general bounded degree planar graph to this case,191.3. Circle packingyielding the following corollary.Corollary (Benjamini and Schramm 1996). Every transient, bounded degree planar graph is non-Liouville.We remark that Benjamini and Schramm also gave a different proof of this theorem using adifferent embedding, the square tiling, for which they also proved a convergence theorem [48].More recently, Angel, Barlow, Gurel-Gurevich, and Nachmias [17] showed that every harmonicfunction on a bounded degree, simple, simply connected triangulation can be represented by afunction on the unit circle in this way.Theorem (Angel, Barlow, Gurel-Gurevich, and Nachmias 2013). Let T be a bounded degree, CPhyperbolic, simple, simply connected triangulation, and let P be a circle packing of T in the unitdisc D. Then the circle packing compactification is a Poisson boundary of T .Recall from earlier that the probabilistic interpretation of this theorem is that the limit pointof the random walk on the unit circle encapsulates all the information about the limiting be-haviour of the random walk. The analogous theorem for square tiling was proven slightly earlierby Georgakopoulos [100].The original proof of this theorem was highly analytic. In order to prove it, the authors employedsophisticated machinery to prove various estimates for random walks on bounded degree circlepackings. Roughly speaking, these estimates allow one to compare the random walk on a boundeddegree circle packing in a domain to a (quasiconformal image of) standard planar Brownian motionin that domain. In particular, the authors proved heat kernel estimates, diffusivity-type estimates,and harmonic measure estimates. These estimates were further developed by Chelkak [69], whosework implies, among other things, that the harmonic measure on the unit disc of a boundeddegree CP hyperbolic triangulation is Ho¨lder continuous. (He considered finite triangulations withboundary; the theorem below follows from his work by taking limits.) Here, given a bounded degreesimple triangulation circle packed in the unit disc, the harmonic measure from v, denoted ωv, isthe law of the limit point in the unit circle of the random walk started at v.Theorem (Chelkak 2013). Let T be a bounded degree, CP hyperbolic, simple, simply connectedtriangulation, let P be a circle packing of T in the unit disc, and let v be such that z(v) = 0. Thenthere exist positive constants α ≤ β and C (depending only on the maximal degree of T ) such thatC−1|I|α ≤ ωv(I) ≤ C|I|βfor every interval I ⊂ ∂D.These estimates are interesting in their own right, and have several further applications. In-deed, they also allowed those authors to prove that the unit circle is the Martin boundary of thetriangulation, a much stronger result that gives a representation formula for all positive harmonic201.3. Circle packingfunctions on the triangulation. Later, they also will play an important role in our calculation,carried out in joint work with Nachmias [130] (Chapter 10 of this thesis), of the critical exponentsfor uniform spanning forests of planar graphs.Theorem (Angel, Barlow, Gurel-Gurevich, and Nachmias 2013). Let T be a bounded degree, CPhyperbolic, simple, simply connected triangulation, and let P be a circle packing of T in the unitdisc D. Then the unit circle is a Martin boundary of T . That is, the following hold.1. For every two vertices u and v of T , the Radon-Nikodym derivative of the harmonic measuresdωvdωu: ∂D→ Ris continuous.2. For every positive harmonic function h on T and every vertex u of T , there exists a uniqueprobability measure µ on ∂D such thath(v) = h(u)∫dωvdωu(ξ) dµ(ξ)for every v ∈ V .It turns out, however, that the heavy machinery developed by Angel, Barlow, Gurel-Gurevich,and Nachmias is not in fact required for the Poisson boundary result. In joint work with YuvalPeres in 2015 [132] (Chapter 8 of this thesis), we proved the following theorem by a much moreelementary argument, which implies the Poisson boundary results for both circle packing and squaretiling.Theorem (H. and Peres 2015). Let G be a planar map, and let z be an embedding of G into adomain D ⊆ D such that 〈z(Xn)〉n≥0 converges to a point in ∂D almost surely, and the law of thelimit point is non-atomic. Then the compactification of G given by taking the closure of z(V ) in Dis a Poisson boundary of G.Thus, once one has established a.s. convergence of the random walk to a boundary point inan embedding of a planar graph in the disc, the identification of the Poisson boundary followsfor free: No further geometric control on the embedding is needed whatsoever. The proof of thistheorem was adapted from our work with Angel, Nachmias, and Ray [21] on unimodular randomtriangulations of unbounded degree, for which the analytic approach was not available.1.3.3 Harmonic Dirichlet functions on planar graphsBesides proving that every transient, bounded degree planar graph is non-Liouville, the Benjamini-Schramm convergence theorem also implies the even stronger result that every transient, boundeddegree planar graph admits non-constant harmonic functions of finite Dirichlet energy.211.3. Circle packingIf f : V → R is a function and Xt is the continuous time random walk3 on G, and we define ftbyft(v) = Ev[f(Xt)],then it turns out that E(ft) is a decreasing function of t. It follows that if f is a function of finiteenergy such that the limitlimn→∞ f(Xn)exists a.s. and is not concentrated on a point (the existence of this limit, and its law if it exists,does not depend on whether we use the continuous or discrete time random walk), thenf∞(v) := Ev[limn→∞ f(Xn)]= limt→∞Evf(Xt)is a non-constant harmonic function with E(f∞) ≤ E(f) < ∞. (In fact, Ancona, Lyons, andPeres [12] proved that the limit of f(Xn) as n → ∞ always exists a.s. whenever f is a Dirichletfunction on a transient graph, from which it is possible to deduce the convergence part of theBenjamini-Schramm convergence theorem.)Now, if P is a circle packing of a bounded degree CP hyperbolic triangulation in the unit disc,then the function z assigning each vertex to its center has finite energy, sinceE(z) ≤∑v∈Vdeg(v)r(v)2 ≤ maxv∈Vdeg(v)∑v∈Vr(v)2 ≤ maxv∈Vdeg(v).Thus, it follows from the Benjamini-Schramm convergence theorem and the above discussion thatevery transient, bounded degree, simply connected, simple plane triangulation admits non-constantharmonic functions of finite Dirichlet energy, namely z∞(v) = Ev[limn→∞ z(Xn)]. With a littleextra work to remove some of these hypotheses, we arrive at the following dichotomy.Corollary (Benjamini and Schramm 1996). Let G be a bounded degree planar graph. Then thefollowing are equivalent.1. G is transient.2. G admits non-constant positive harmonic functions.3. G is non-Liouville, i.e., admits non-constant bounded harmonic functions.4. G admits non-constant harmonic functions of finite Dirichlet energy.The implications (4) ⇒ (3) ⇒ (2) ⇒ (1) hold on any graph. We shall later see that an evenmore far reaching dichotomy holds for unimodular random planar maps, without the assumptionof bounded degree.3This is the walk that has a semigroup of transition operators given by Pt = e−t∆, where ∆ = ∇∗∇ is theLaplacian of G221.3. Circle packingLet us take a moment to mention a relevant work in progress. Now that we know that non-constant harmonic Dirichlet functions exist on any bounded degree, CP hyperbolic, simple, properplane triangulation, it is natural to wonder whether there is a geometric representation for the spaceof all such functions, as we had for the spaces of bounded harmonic functions and positive harmonicfunctions. In upcoming work, we give such a representation. For each function f : ∂D → R, wedefineD(φ) := 14pi2∫∂D∫∂D∣∣∣∣∣ φ(ξ)− φ(ζ)2 sin (12 |ξ − ζ|)∣∣∣∣∣2dξ dζ <∞.where the integrals are taken with respect to arc length, and say f is Douglas-integrable ifD(f) <∞. The space of Douglas-integrable functions is a Hilbert space with the inner productf(o)g(o) +D(f, g) = f(o)g(o) + 14pi2∫∂D∫∂D(f(ξ)− f(ζ))(g(ξ)− g(ζ)))2 sin(12 |ξ − ζ|) dξ dζ,where o ∈ V is an arbitrary root vertex. In fact, D(f) is exactly the Dirichlet energy of theharmonic extension of f to the unit disc.Theorem (H. 2017+). Let T be a transient, bounded degree, proper plane triangulation, and let Pbe a circle packing of T in the unit disc. Then the functionf 7−−→ h, where h(v) = Ev f(limn→∞Xn)is a bounded linear isomorphism from the space of Douglas-integrable functions on ∂D to the spaceof harmonic Dirichlet functions on T .By a bounded linear isomorphism we mean a bounded linear map with a bounded linear inverse,and not necessarily an isometry.A potentially surprising thing here is that the space of Douglas-integrable functions on theboundary is always the same; the expression for the Douglas energy does not involve the harmonicmeasure, or otherwise involve the triangulation in any way.1.3.4 Double circle packingBefore moving on, let us mention a generalisation of the circle packing theorem which, in ouropinion, is even more beautiful.Let M be a planar map with vertex set V and face set F . A double circle packing of M isa pair of circle packings P = {P (v) : v ∈ V } and P † = {P †(f) : f ∈ F} satisfying the followingconditions (see Figure 1.6):1. (M is the tangency map of P .) For each pair of vertices u and v of M , the discs P (u)and P (v) are tangent if and only if u and v are adjacent in M . Moreover, for each vertex u,the discs corresponding to the vertices adjacent u appear around P (u) in the clockwise orderspecified by the map structure σu.231.3. Circle packingFigure 1.6: A polyhedral planar map and its double circle packing.2. (M † is the tangency map of P †.) For each pair of faces f and g of G, the discs P †(f) andP †(g) are tangent if and only if f and g are adjacent in G†. Moreover, for each face f , thediscs corresponding to the vertices adjacent f appear around P †(f) in the clockwise orderspecified by the map structure σ†f .3. (Primal and dual circles are perpendicular.) For each vertex v and face f of M , thediscs P †(f) and P (v) have non-empty intersection if and only if f is incident to v, and in thiscase the boundary circles of P †(f) and P (v) intersect at right angles.Recall that a graph is 3-connected if the removal of any two vertices from the graph does not causethe graph to become disconnected. We call a map that is both simple and 3-connected polyhedral.Any embedding of a planar map that is not polyhedral must contain faces that are not convex,and it follows that any finite planar map admitting a double circle packing must be polyhedral.Conversely, Thurston’s interpretation of Andreev’s Theorem [179, 221] implies that every finite,polyhedral, planar map admits a double circle packing (see also [58]). The corresponding infinitetheory was developed by He [120], who proved that every infinite, polyhedral, simply connectedmap M with locally finite dual admits a double circle packing in either the Euclidean plane or thehyperbolic plane (but not both) and that this packing is unique up to Mo¨bius transformations. Asbefore, we say that M is CP parabolic or CP hyperbolic as appropriate.In our work with Nachmias [130], we proved a form of the Ring Lemma for double circle packings.We write v ⊥ f to mean that the vertex v is incident to the face f .Theorem (H. and Nachmias 2016). There exists a family of positive constants 〈kn,m : n ≥ 3,m ≥ 3〉such that if (P, P †) is a double circle packing of a polyhedral planar map M in a domain D ⊆ C∪{∞}and v is a vertex of M such that P (v) does not contain ∞, thenr(v)/r(f) ≤ kdeg(v),maxg⊥v deg(g)for all f ∈ F incident to v.241.3. Circle packingOnce the existence and uniqueness theorems and the Ring Lemma are in place, everything elsethat we have said about circle packings of simple triangulations extends more or less immediately todouble circle packings of polyhedral maps of bounded codegree. In particular, as in the He-SchrammTheorem [121], CP hyperbolicity is equivalent to transience for simply connected polyhedral mapswith bounded degrees and codegrees [120].1.3.5 Circle packing and the degreeAn interesting aspect of circle packing is that, in certain situations, we can deduce the CP type ofa triangulation from the degrees of its vertices. This was first observed by Beardon and Stephenson[34], who proved the following.Theorem (Beardon and Stephenson 1991). Let T be an infinite, simple, simply connected trian-gulation. If deg(v) ≤ 6 for every vertex v of T , then T is CP parabolic. If deg(v) ≥ 7 for everyvertex v of T , then T is CP hyperbolic.Exercise. Show that there exists a constant C > 1 such that the following holds. Suppose T is asimple triangulation circle packed in a domain D ⊆ C. Then1. for every vertex v of T with deg(v) ≤ 5, there is a neighbour u of v such that r(u)/r(v) ≥ C.2. for every vertex v of T with deg(v) = 6, there is a neighbour u of v such that r(u)/r(v) ≥ 1and a neighbour w of v such that r(w)/r(v) ≤ 1.3. for every vertex v of T with deg(v) ≥ 7, there is a neighbour u of v such that r(u)/r(v) ≤ C−1.Let rH(v) denote the hyperbolic radius of a disc P (v) ⊂ D.Exercise. Show that there exists a constant C > 1 such that the following holds. Suppose Tis a simple triangulation circle packed in a domain D ⊆ D. Then for every vertex v of T withdeg(v) ≤ 6, there is a neighbour u of v such that rH(u)/rH(v) ≥ C.Exercise. Deduce the above theorem of Beardon and Stephenson from the previous two exercises.We shall later see that for unimodular random simply connected triangulations, the circle pack-ing type is determined by the average degree.251.4. Percolation1.4 PercolationIn Bernoulli bond percolation, each edge of a (usually infinite) graph G is chosen randomly tobe either deleted with probability 1 − p, or else retained with probability p. The random graphobtained in this way is denoted G[p]. Connected components of G[p] are referred to as clusters.Although we will have relatively little new to say about percolation in this thesis, the theoryof percolation provides important motivation for our work on uniform spanning forests, and alsoleads naturally to the theory of unimodular random rooted graphs, another central topic of thisthesis. Percolation has become a topic of central importance to modern probability theory, andhas a huge literature surrounding it. The reader is referred to the beautiful, if slightly outdated,monograph of Grimmett [106] for a thorough treatment of the Euclidean (Zd) theory, and to [173]for the theory of percolation on more general graphs.The first basic result about percolation, without which the model would not be nearly asinteresting, is that for most graphs, percolation undergoes a non-trivial phase transition, meaningthat the critical probability,pc(G) = inf{p ∈ [0, 1] : G[p] has an infinite cluster almost surely},is strictly between zero and one. Conjecturally, pc ∈ (0, 1) for every transitive graph that is notrough isometric to Z: This has been resolved in most cases, and remains open only for transitivegraphs of intermediate volume growth (i.e., subexponential but superpolynomial). For example, asimple first moment argument shows that pc > 0 for any bounded degree graph, since the expectednumber of open simple paths of length n starting at a vertex v is at mostpn(maxu∈Vdeg(u))n,which yields the bound pc ≥ (maxu∈V deg(u))−1. For Z2, a similar first moment argument withsimple curves surrounding the origin (known as a Peierls argument [189]) shows that pc(Z2) < 1,while for d ≥ 2 we clearly have that pc(Zd) ≤ pc(Z2).The study of percolation can naturally be decomposed into the study of the subcritical (p < pc),critical (p = pc), and supercritical (p > pc) regimes. Here, we shall be interested mostly in thecritical and supercritical regimes.At criticality, the central question concerns the existence or nonexistence of an infinite cluster.Indeed, perhaps the best known open problem in modern probability theory is to prove that thereis no infinite cluster at criticality on Zd for all d ≥ 2. This problem was solved in two dimensionsby Russo in 1981 [203], and for all d ≥ 19 by Hara and Slade in 1994 [117]. More recently, Fitznerand van der Hoftstad [89] sharpened the methods of Hara and Slade to solve the problem for alld ≥ 11. (It is expected that this method can in principle, and with great effort, be pushed to handleall d ≥ 7. Dimensions 3, 4, 5, and 6 are expected to require new approaches.)261.4. PercolationIn 1996, Benjamini and Schramm [51] proposed a systematic study of percolation on generaltransitive (and quasi-transitive) graphs. They made several conjectures and posed many questions.Here is one of them.Conjecture (Benjamini and Schramm 1996). Let G be a transitive graph. If pc(G) < 1, then G[pc]does not have any infinite clusters almost surely.It quickly emerged that it is often substantially easier to study percolation on unimodulartransitive graphs than on general transitive graphs. A transitive graph G = (V,E) is said to beunimodular if for every function F : V 2 → [0,∞] that is automorphism equivariant in the sensethat F (γu, γv) = F (u, v) for every u, v ∈ V and every automorphism γ of G, then, letting ρ be afixed root vertex of G, ∑v∈VF (ρ, v) =∑u∈VF (u, ρ). (1.4.1)The equality (1.4.1) is referred to as the Mass-Transport Principle (MTP)4. We think of F asa rule for sending a non-negative amount of mass from each vertex to each other vertex, so thatthe mass-transport principle says thatmass out of the root = mass into the root .It turns out that most transitive graphs one encounters ‘in the wild’ are unimodular. In particular,every amenable transitive graph, every Cayley graph of a finitely generated group, and everytransitive, simply connected, planar map with locally finite dual has the property of unimodularity.Figure 1.7: The grand-parent graph.An example of a transitive graph that is not unimodular is thegrandparent graph, defined as follows. Take a 3-regular tree, anddraw it in the plane so that every vertex has one ‘parent’ above it andtwo ‘children’ below it. The grandparent graph is formed by addingto the 3-regular tree an edge connecting each vertex to its grandpar-ent, that is, the parent of its parent. We can define an automorphismequivariant function on the grandparent graph byF (u, v) = 1(v is u’s grandparent).Since every vertex has one grandparent but four grandchildren, we have∑v∈VF (ρ, v) = 1 but∑u∈VF (u, ρ) = 4,so that the Mass-Transport Principle does not hold for the grandparent graph.4The history of this definition is as follows: A locally compact group is said to be unimodular if its left and rightHaar measures coincide. A transitive graph is unimodular in our sense if and only if its group of automorphisms hasa transitive unimodular subgroup.271.4. PercolationA major achievement in the theory of critical percolation outside of the Euclidean setting wasmade in 1999 by Benjamini, Lyons, Peres, and Schramm [43]. This theorem came out of work [45]by a subset of the same authors on arbitrary (non-Bernoulli) automorphism invariant percolationprocesses, which we shall have more to say about later.Theorem (Benjamini, Lyons, Peres, and Schramm 1999). Let G be a nonamenable, unimodular,transitive graph. Then G[pc] has no infinite clusters almost surely.Partial progress was made in the nonunimodular case by Peres, Pete, and Scolnicov [192], whoproved there are no infinite clusters at criticality a.s. on certain well-known examples of nonuni-modular transitive graphs, including decorated trees (like the grandparent graph) and nonamenableDiestel-Leader graphs, and by Tima´r [222], who proved that there is at most one infinite cluster atcriticality on any nonunimodular transitive graph a.s.In 2016 [129] (Chapter 2 of this thesis), we found an elementary proof that the following estimateholds in any transitive graph:inf{P(x is connected to y in G[pc]): x, y ∈ V, d(x, y) ≤ n}≤(lim infr→∞ |B(x, r)|1/r)−n.This estimate readily implies that there cannot be a unique infinite cluster at pc in any transitivegraph of exponential growth. However, the existence of multiple infinite clusters at criticality hadalready been ruled out by previous work (the amenable and unimodular nonamenable cases arediscussed in the following subsection, while the nonunimodular case is handled by the work ofTima´r mentioned above). Thus, we obtained the following theorem.Theorem (H. 2016). Let G be a transitive graph with exponential growth. Then G[pc] has noinfinite clusters almost surely.1.4.1 The number of infinite clustersLet us now turn to the supercritical regime. In this regime, we are particularly interested inunderstanding the geometry of the infinite clusters of G[p]. The most basic question concerns thenumber of infinite clusters. For this question, the foundational result was proven by Newman andSchulman in 1981 [187].Theorem (Newman and Schulman 1981). Let G be a transitive graph. Then G[p] has either noinfinite clusters, a unique infinite cluster, or infinitely many infinite clusters almost surely for everyp ∈ [0, 1].The key to this theorem is the insertion tolerance of Bernoulli percolation, which says thatfor any set of edges A and p > 0, the law of the subgraph G[p] ∪ A is absolutely continuous5 withrespect to the law of G[p].5Recall that the law of a random variable X is said to be absolutely continuous with respect to the law of arandom variable Y if whenever A is a set such that Y is a.s. not in A , then X is also a.s. not in A .281.4. PercolationThe proof is as follows: Given a configuration ω ∈ {0, 1}E and an automorphism γ of G, defineγω(e) = ω(γ−1(e))for every edge e. It is an easy fact that Bernoulli bond percolation on any transitive graph isergodic, meaning that if A ⊆ {0, 1}E is a set of configurations that is automorphism invariant inthe sense thatω ∈ A ⇒ γω ∈ Afor every configuration ω and automorphism γ, then we must have that P(G[p] ∈ A ) is eitherzero or one. In particular, the number of infinite components is automorphism invariant, and wededuce that the number of infinite components is not random. That is, for every p, there existsNp ∈ N ∪ {∞} such that G[p] has Np infinite clusters a.s.Suppose for contradiction that Np /∈ {0, 1,∞}. If we take a large connected set of edges A,then with high probability A is incident to more than one of the infinite clusters of G[p]. Thus,the configuration G[p]∪A has positive probability to have strictly fewer infinite clusters than G[p].But G[p] ∪ A is absolutely continuous with respect to G[p] by insertion-tolerance, hence it musthave Np infinite clusters a.s., yielding a contradiction.The Newman-Schulman Theorem can in fact be extended to any insertion-tolerant automor-phism invariant percolation on a transitive graph. Here, an automorphism-invariant percolationis a random subgraph ω of G such that γω has the same distribution as ω for every automorphism γof G. (In the case that ω is also ergodic the Newman-Schulman Theorem follows exactly as above.In general, it is possible to reduce to the ergodic case by taking an ergodic decomposition, whichpreserves insertion tolerance.)The next major result on the number of clusters was due to Aizenmann, Kesten, and Newmanin 1987 [3], who proved that percolation on Zd has at most one infinite cluster a.s. for every d ≥ 1.A much simpler proof of this theorem was found by Burton and Keane in 1989 [64], which wasthen generalised to all transitive amenable graphs by Gandolfi, Keane, and Newman in 1992 [97].Like the Newman-Schulman Theorem, this theorem also extends to arbitrary insertion-tolerant,automorphism invariant percolations.Theorem. Let G be an amenable transitive graph, and let p ∈ [0, 1]. Then G[p] has at most oneinfinite cluster almost surely.It is a major open problem, first stated by Benjamini and Schramm [51], to prove that theconverse holds. The uniqueness threshold is defined to bepu(G) = inf{p ∈ [0, 1] : G[p] has a unique infinite cluster almost surely}.Conjecture (Benjamini and Schramm 1996). Let G be a transitive graph. Then pc < pu if andonly if G is nonamenable.291.4. PercolationNot much progress has been made on this question; see [112] and [173, Chapter 9] for an accountof what is known.Since the existence of a unique infinite cluster is not monotone with respect to the configuration,the following theorem, due to Schonmann [205], and Ha¨ggstro¨m, Peres, and Schonmann [114], isfar from obvious.Theorem (Ha¨ggstro¨m, Peres, and Schonmann 1999). Let G be a transitive graph, and let p2 > p1.If G[p1] has a unique infinite cluster almost surely, then G[p2] has a unique infinite almost surely.In the unimodular case, this theorem can also be deduced from the following beautiful theorem ofLyons and Schramm [176], which, informally, says that infinite clusters of Bernoulli bond percolationon a unimodular transitive graph all ‘look the same’. The theorem extends to insertion-tolerantautomorphism invariant percolations.Theorem (Lyons and Schramm 1999). Let G be a unimodular transitive graph, let p ∈ [0, 1], andlet A ⊆ {0, 1}E be a measurable, shift invariant set. Then either every infinite cluster of G[p] isin A or no infinite clusters of G[p] are in A almost surely.For example, the theorem implies that either every infinite cluster of G[p] is transient or everyinfinite cluster of G[p] is recurrent a.s.The main idea of the proof of the Lyons-Schramm Indistinguishability Theorem can be sum-marised as follows. The coexistence of infinite clusters of different types (i.e., of infinite clusters inA and not in A ) can be shown to imply that for some infinite cluster, there exist infinitely manypivotal edges, that is, closed edges that change the type of the cluster if they are inserted. Heuristi-cally, this should contradicts the measurability of the property: The existence of pivotal edges faraway from the origin – which by insertion tolerance are in some sense indifferent to being insertedand hence changing the type of an infinite cluster – should imply that we cannot approximate theevent that the cluster at the origin is in A by an event depending only on finitely many edges ofthe configuration. (The ability to approximate a set in this way is the definition of the set beingmeasurable.)To see that the Lyons-Schramm Indistinguishability Theorem implies the Ha¨ggstro¨m-Peres-Schramm Uniqueness Monotonicty Theorem in the unimodular case, first observe that we cansample G[p1] by first sampling G[p2], and then performing Bernoulli p1/p2 bond percolation onG[p2]. Consider the setA =ω ∈ {0, 1}E : ω spans a connected subgraph H of G such that Bernoullip1/p2 percolation on H has no infinite clusters almost surelyIf G[p2] has infinitely many infinite clusters a.s., then, by the Lyons-Schramm IndistinguishabilityTheorem, either all these clusters are in A , in which case G[p1] has infinitely many infinite clusters301.4. Percolationa.s. also, or else none of the clusters are in A , in which case G[p1] does not have any infinite clustersa.s., concluding the proof.Indistinguishability of infinite clusters can fail for nonunimodular transitive graphs. However,Ha¨ggstro¨m, Peres, and Schonmann [114] proved that indistinguishability still holds in this contextprovided that we restrict attention to what they called robust properties, of which the set A aboveis an example.1.4.2 The geometry of infinite clustersWhat can we say about the geometry of individual clusters? In general, we expect that if G[p] hasa unique infinite cluster, then this cluster will be similar to the original graph G in many ways.For example, it is conjectured that if G is a transient transitive graph, then every infinite cluster ofG[p] is transient a.s. for every p > pc. The first result of this form was due to Grimmett, Kesten,and Zhang [104].Theorem (Grimmett, Kesten, and Zhang 1993). Let p > pc(Zd). Then the unique infinite clusterof Zd[p] is transient almost surely.The original proof of this theorem was rather difficult. A much simpler proof was found byGabor Pete in 2008 [194], using isoperimetric techniques. An obstacle to applying isoperimetricmethods to percolation is that the infinite percolation cluster will necessarily contain ‘bad regions’.In particular, if G is a transitive graph and p < 1, it is easily seen that every infinite cluster of G[p]must contain arbitrarily large sets of vertices with only one edge in their boundary. This is becausesuch sets have positive probabilities to occur at the origin, and therefore must occur somewhere byergodicity.This difficulty led Benjamini, Lyons, and Schramm [45] to introduce the notion of the anchoredisoperimetric inequalities, whose definition we already saw in Section 1.2.2. These are less sensitiveto perturbations of the graph, and we can hope that if G is a sufficiently nice (e.g. transitive) graphthat satisfies an anchored φ(t)-isoperimetric inequality, then the infinite clusters of G[p] will alsosatisfy an anchored φ(t)-isoperimetric inequality for p > pc. Chen and Peres [70] proved that thisis indeed the case for graphs with anchored expansion, at least for sufficiently large p. A secondproof, due to Pete, appeared as an appendix to the same paper.Theorem (Chen, Peres, and Pete 2004). Let G be a graph with anchored expansion. Then thereexists p0 < 1 such that every infinite cluster of G[p] has anchored expansion almost surely for everyp ≥ p0.A much more general form of this result was later proven by Pete [194], a special case of whichis as follows.Theorem (Pete 2008). Let G be a Cayley graph of a finitely presented group (e.g. Zd) that isnot rough isometric to Z, and suppose that G satisfies a φ(t)-isoperimetric inequality for some311.5. Uniform spanning forestsincreasing φ. Then there exists p0 < 1 such that every infinite cluster of G[p0] satisfies an anchoredφ(t)-isoperimetric inequality almost surely.By the Thomassen Criterion, these results imply that infinite clusters of G[p] are transient forsufficiently large p for a large class of transient graphs G. In the case of Zd, it is possible to recoverthe full Grimmett-Kesten-Zhang Theorem by a renormalization argument.Now suppose that G is non-Liouville. Does it follow that every infinite cluster of G[p] is non-Liouville for every p > pc. Conversely, if G is Liouville, does it follow that every infinite cluster ofG[p] is Liouville for every p > pc? In general, this question is very poorly understood. (In contrast,the existence of harmonic Dirichlet functions on percolation clusters of unimodular transitive graphsis very well understood since the work of Gaboriau [94].) Similarly to the case of transitive graphs,the non-Liouville property for percolation clusters on unimodular transitive graphs is equivalentto the random walk on the cluster having positive speed. Thus, we can answer the question inthe nonamenable unimodular case for large p by invoking the following beautiful theorem of Vira´g[227]. We shall see that much easier proofs, avoiding anchored expansion altogether, are possibleonce we introduce the notion of invariant nonamenability.Theorem (Vira´g 2000). Let G be a bounded degree graph with anchored expansion. Then therandom walk on G has positive speed almost surely, and for each vertex v there exist positiveconstants c and C such thatpn(v, v) ≤ Ce−cn1/3for all n ≥ 1.1.5 Uniform spanning forestsThe Free Uniform Spanning Forest (FUSF) and the Wired Uniform Spanning Forest(WUSF) of an infinite graph G are defined as weak limits of the uniform spanning trees on largefinite subgraphs of G, taken with either free or wired boundary conditions respectively. Firststudied by Pemantle [190], the USFs are closely related many other areas of probability, includingelectrical networks [62, 154], Lawler’s loop-erased random walk [44, 161, 228], sampling algorithms[197, 228], domino tiling [150], the Abelian sandpile model [137, 138, 178], the rotor-router model[126], and the Fortuin-Kasteleyn random cluster model [105, 109]. The USFs are also of interestin group theory, where the FUSFs of Cayley graphs are related to the `2-Betti numbers [94, 169]and to the fixed price problem of Gaboriau [95], and have also been used to approach the Dixmierproblem [87].Uniform spanning forests are also the major topic of this thesis, being the subject of four ofthe included papers and being of central importance in one other. One of our main goals will beto address the same questions for the uniform spanning forests that we asked about percolation inthe previous section.321.5. Uniform spanning forests1.5.1 Uniform spanning treesLet us start at the beginning. A uniform spanning tree of a finite graph G is simply a uniformrandom element from the set of spanning trees of G, that is, connected subgraphs of G that containevery vertex and no cycles. The connection between uniform spanning trees and electrical networksgoes back as far as it could, all the way to the 1847 work of Kirchhoff [154] in which the laws ofelectrical networks were introduced.Theorem (Kirchhoff’s effective resistance formula). Let G be a finite graph. Then for every edgee of G,P(e is in a uniform spanning tree of G) = Reff(e− ↔ e+)(Kirchhoff did not state this theorem probabilistically, but rather as a statement about the ratioof the number of spanning trees that include the edge to the total number of spanning trees.)Kirchhoff’s interest in this theorem was computational: He also invented a method to computethe number of spanning trees of a graph, the famous Matrix-Tree Theorem.Theorem (Kirchhoff’s Matrix-Tree Theorem). Let G be a finite connected graph with n vertices,and let λ1, . . . , λn−1 be the non-zero eigenvalues of the Laplacian of G. Then|{spanning trees of G}| = 1nn−1∏i=1λi.Since the number of spanning trees that do not contain a given edge is equal to the numberof spanning trees of the graph in which that edge has been deleted, Kirchhoff’s effective resistanceformula together with the Matrix-Tree theorem give a method for computing effective resistancesin finite graphs. From our perspective, we will be more interested in using the formula the otherway around, using the variational principles for the effective resistance to estimate the probabilitythat an edge is in a uniform spanning tree (or forest).How can we sample the uniform spanning tree of a finite graph? One very simple method isas follows. Pick some edge of the graph. We can compute the probability that the edge is in theuniform spanning tree (e.g. using the Matrix-Tree Theorem), and flip an appropriately biased cointo decide whether or not to include it. If we decide to include the edge, then we next contractit, i.e., identify the two endpoints of the edge. Otherwise, if we decided not to include the edge,we delete it from the graph. We then continue as in the first step, choosing another edge fromthe graph, choosing whether or not to include it by performing a Matrix-Tree calculation (in themodified graph) and flipping an appropriately biased coin, and then contracting or deleting theedge as appropriate. If we continue doing this until we have decided what to do with every edge,then the set of edges we chose to include will form a uniformly random spanning tree of G.Exercise. Prove that this algorithm works.331.5. Uniform spanning forestsA far-reaching extension of Kirchhoff’s effective resistance formula, known as the Transfer-Current Theorem of Burton and Pemantle [62], allows one to calculate the probability that anyset of edges is included in the forest in terms of electrical quantities. (The case of two edgeshad previously been studied by Brooks, Smith, Stone, and Tutte [60], who were interested by theconnection to square tiling, which they invented.) Given two oriented edges e1 and e2, we defineY (e1, e2) to be the current flowing through e2 when a unit potential is placed on the endpoints ofe1. In other words,Y (e1, e2) = Pe+2(τ+e+1< τ+e−1)−Pe−2(τ+e+1< τ+e−1).We fix arbitrarily an orientation of each edge e, and think of Y as a matrix indexed by E × E,which we call the transfer-current matrix.Theorem (Burton and Pemantle 1993). Let G be an infinite graph. Then for any collection ofedges e1, . . . , en of G, we haveUST({e1, . . . , en} ⊆ T ) = det〈Y (ei, ej)〉1≤i,j≤n.Note that the probabilities of all other events can be computed from the probabilities of theevents of the form {{e1, . . . , en} ⊆ T} using inclusion-exclusion.1.5.2 Sampling using random walksThe Aldous-Broder AlgorithmLet G be a finite graph, and let 〈Xn〉n≥0 be a random walk on G. For each vertex v of G, lete(v,X) be the oriented edge pointing into v that is crossed by the walk X as it enters v for thefirst time, and defineAB(X) = {−e(v,X) : v 6= X0}to be the collection of (reversed) first entry edges. It is not hard to see that AB(X) is a spanningtree, where the edges of the tree are oriented so that every vertex other than X0 has exactly oneoriented edge in the tree emanating from it. The following theorem, however, is surprising at first.Theorem (Broder 1989, Aldous 1990). AB(X) is a uniform spanning tree of G.Note in particular that we can start the walk wherever we want, and this does not change thedistribution of the tree. This theorem gives another method of sampling the uniform spanning treeof a finite graph, named the Aldous-Broder algorithm after its inventors [8, 59].Exercise. Use the Aldous-Broder algorithm to prove Kirchhoff’s effective resistance formula.Wilson’s algorithmThe loop-erasure of a path in a graph is formed by erasing cycles from the path chronologicallyas they are created. (The loop-erasure is only defined for paths that are either finite or transient341.5. Uniform spanning forestsin the sense that they visit each vertex of the graph at most finitely often.) The loop-erasure ofsimple random walk is called loop-erased random walk, and was first studied by Lawler [161].Let {v0, v1, . . . , vn} be an enumeration of the vertices of a finite graph G and define a sequence oftrees Ti in G as follows:1. Let T0 have vertex set v0 and no edges.2. Given Ti, start an independent random walk from vi+1 stopped when it hits the set of verticesalready included in the tree Ti.3. Form the loop-erasure of this random walk path and let Ti+1 be the union of Ti with thisloop-erased path.4. Let T = Tn =⋃ni=1 Ti.Again, this algorithm clearly produces a spanning tree of G. Once again, however, the followingtheorem is very surprising. It is even surprising that the distribution of the tree T does not dependon the enumeration we chose.Theorem (Wilson 1996). The random tree T is a uniform spanning tree of G.Wilson’s proof [228] uses an ingenious notion of ‘cycle popping’, of which the above algorithm ismerely one implementation. A major advantage of Wilson’s algorithm over the Aldous-Broder al-gorithm is that it readily extends to generate the wired uniform spanning forest of an infinite graph.This led to a surge of progress on the wired uniform spanning forest following its introduction, inparticular the landmark work of Benjamini, Lyons, Peres, and Schramm [44].1.5.3 Uniform spanning forestsWe now define the free and wired uniform spanning forests of an infinite graph. These will bedefined as weak limits over exhaustions. These weak limits were both implicitly proven to exist byPemantle [190] in 1991, although the wired uniform spanning forest was not considered explicitlyuntil the work of Ha¨ggstro¨m [109] in 1995.We write USTG for the law of the uniform spanning forest of finite graph G. The free uniformspanning forest measure FUSFG is defined to be the weak limit of the sequence 〈USTGn〉n≥1, sothatFUSFG(S ⊂ F) = limn→∞USTGn(S ⊂ T ).for each finite set S ⊂ E, where F is a sample of the FUSF of G and T is a sample of the UST ofGn. The wired uniform spanning forest measure WUSFG is defined to be the weak limit of thesequence 〈USTG∗n〉n≥1, so thatWUSFG(S ⊂ F) = limn→∞USTG∗n(S ⊂ T )351.5. Uniform spanning forestsfor each finite set S ⊂ E, where F is a sample of the WUSF of G and T is a sample of the UST ofG∗n.The existence of these limits follow immediately from the Transfer-Current Theorem, togetherwith what we know about infinite electrical networks, since, for example, we know that currentson Gn converge to free currents on G and hence that the transfer-current matrix on Gn convergesto the free transfer current matrix on G (defined in the obvious way). The wired case is similar.In particular, Kirchhoff’s effective resistance formula and the transfer-current theorem extend toboth the wired and free uniform spanning forests in the natural way. This point of view was notavailable to Pemantle at the time of his original work, but was available to Benjamini, Lyons, Peres,and Schramm [44], who reproved convergence in this way and deduced the following theorem.Theorem (Benjamini, Lyons, Peres, and Schramm 2001). Let G be an infinite graph. Then the freeand wired uniform spanning forests of G coincide if and only if G does not admit any non-constantharmonic functions of finite Dirichlet energy.In particular, we have that the free and wired forests coincide in any amenable transitive graphand that, by the theorems of Benjamini and Schramm [47, 48] stated in Section 1.3.3, we have thatthe free and wired uniform spanning forests of a bounded degree planar graph are different if andonly if the graph is transient.1.5.4 The number of trees in the wired forestAlthough they are defined as limits of trees, the uniform spanning forests of a graph need not beconnected. Indeed, we have the following theorem of Pemantle [190].Theorem (Pemantle 1991). The uniform spanning forest of Zd is connected if and only if d ≤ 4.Why is dimension four important? A much clearer picture emerged following the introductionof Wilson’s algorithm. In their seminal paper [44], Benjamini, Lyons, Peres, and Schramm showedhow to extend Wilson’s algorithm to generate the wired uniform spanning forest of any transientgraph. (It is obvious how to extend both the Aldous-Broder algorithm and Wilson’s algorithmto infinite recurrent graphs.) This allowed them to prove many things. Their extension, calledWilson’s algorithm rooted at infinity, can be described as follows. Let G be a transient graphand let 〈vi〉i≥1 be an enumeration of its vertices. Define a sequence of trees Fi in G as follows:1. Let F0 be the empty forest, that has no vertices or edges.2. Given Fi, start an independent random walk from vi+1 stopped when it hits the set of verticesalready included in the tree Fi. If the walk never hits this set, then it runs forever.3. Form the loop-erasure of this random walk path and let Fi+1 be the union of Fi with thisloop-erased path.4. Let F =⋃i≥1 Fi.361.5. Uniform spanning forestsGiven the correctness of Wilson’s algorithm, the following is fairly easy to verify from the definitions.(Simply consider running Wilson’s algorithm on each G∗n with v0 = ∂n and the other verticesappearing in the order specified, and take the limit as n→∞.)Theorem (Benjamini, Lyons, Peres, and Schramm 2001). Let G be a transient graph. Then therandom forest F generated by Wilson’s algorithm rooted at infinity is a wired uniform spanningforest of G.Using this algorithm, Benjamini, Lyons, Peres, and Schramm were able to prove the followingtheorem. We say that a graph G has the intersection property if whenever X and Y areindependent random walks on G, their traces {Xn : n ≥ 0} and {Yn : n ≥ 0} have non-emptyintersection a.s. (or, equivalently, if the traces have infinite intersection a.s.). We say that G hasthe non-intersection property if the traces instead have only finite intersection a.s.Theorem (Benjamini, Lyons, Peres, and Schramm 2001). Let G be an infinite graph. Then thewired uniform spanning forest of G is connected a.s. if and only if G has the intersection property.If G has the non-intersection property, then the wired uniform spanning forest of G has infinitelymany components almost surely.Perhaps this seems that it should be obvious from Wilson’s algorithm, but it is not. Whatis obvious is that the WUSF is connected if and only if a random walk almost surely intersectsan independent loop-erased random walk. The fact that these two properties are equivalent wasproved in a companion paper by Lyons, Peres, and Schramm [174], using a clever second momentargument adapted from the work of Fitzsimmons and Salisbury [90, 204].It can be shown that every transitive graph either has the intersection property or the non-intersection property, yielding the following theorem, which is an analogue of the Newman-Schulmantheorem from percolation.Corollary (Benjamini, Lyons, Peres, and Schramm 2001). Let G be a transitive graph. Then thewired uniform spanning forest of G is either connected or has infinitely many connected componentsalmost surely.Moreover, it can be shown that a transitive graph has the intersection property if and only if∑n≥1npn(v, v) =∞for some (and hence every) vertex v. Once all this is in place, Pemantle’s theorem follows fromPo´lya’s estimate (1.2.1). (The fact that Zd has the intersection property if and only if d ≤ 4 wasoriginally proved by Erdo¨s and Taylor in 1960 [88].) More generally, we deduce that the wireduniform spanning forest is disconnected a.s. in any transitive graph satisfying a 5-dimensionalisoperimetric inequality.371.5. Uniform spanning forestsGreatly extending Pemantle’s theorem, Benjamini, Kesten, Peres and Schramm [41] discoveredthat the transition between connectivity and disconnectivity in dimension four is merely the first ofan infinite family of related transitions occurring every four dimensions. In joint work with YuvalPeres [134] (not included in this thesis), we extended this theorem, and developed a detailed pictureof how the adjacency structure of the trees in the USF of Zd varies as a function of d. In particular,we showed that the adjacency structure of the forest undergoes a qualitative change every time thedimension increases and is above four, rather than just every four dimensions.1.5.5 Geometry of trees in the wired forestAfter connectivity, the most basic property of a forest is the number of ends its components have.Recall that we defined the space of ends of a tree in Section 1.2.4. Components of the WUSF areone-ended a.s. in many large classes of graphs. Generally speaking, we expect that components ofthe WUSF will be one-ended a.s. in any transient graph that we have not constructed to serve as acounterexample. The first generally applicable one-endedness theorem was proven using Wilson’salgorithm by Benjamini, Lyons, Peres, and Schramm [44].Theorem (Benjamini, Lyons, Peres, and Schramm 2001). Let G be a unimodular transitive graphthat is not rough isometric to Z. Then every component of the wired uniform spanning forest of Gis one-ended almost surely.Their proof analysed the recurrent and transient cases separately. The proof in the transientcase involved an innovative use of the mass-transport principle, the discovery of which was recountedin the following memorable anecdote of Russ Lyons [1].To me, Oded’s most distinctive mathematical talent was his extraordinary clarity ofthought, which led to dazzling proofs and results. Technical difficulties did not obscurehis vision. Indeed, they often melted away under his gaze. At one point when the fourof us [Oded Schramm, Russ Lyons, Itai Benjamini, and Yuval Peres] were working onuniform spanning forests, Oded came up with a brilliant new application of the Mass-Transport Principle. We were not sure it was kosher, and I still recall Yuval asking meif I believed it, saying that it seemed to be “smoke and mirrors.” However, when Odedexplained it again, the smoke vanished.Let us now briefly explain their proof. They begin with a relatively straightforward applicationof the mass transport principle to deduce that every component has at most two ends. For thispart of the proof, they observe that there is a natural (in particular, automorphism invariant)oriented version of the WUSF of a transient graph, in which every vertex has exactly one orientededge emanating from it in the forest. This can be defined by orienting towards the boundaryvertex when taking the weak limit, or equivalently by orienting edges of the forest according tothe direction they are traversed by the loop-erased random walks used to generate the forest whenrunning Wilson’s algorithm. Define the core of a forest to be the set of vertices that lie on some381.5. Uniform spanning forestssimple bi-infinite path in the forest (which is empty if and only if every tree in the forest is finiteor one-ended). The core of a two-ended tree is a bi-infinite path which we call the trunk. Let Fbe the OWUSF of a transient unimodular transitive graph. Observe that the unique oriented edgein F emanating from a vertex in the core of F must have its other endpoint in the core also. Definea mass transportf(u, v)= P(u is in the core, v is the endpoint of the unique oriented edge emanating from u in F).Then we have that ∑vf(o, v) = P(o is in the core)and ∑vf(v, o) = E|{v in the core : the oriented edge emanating from v points into o}|= E[(|{v in the core : v is adjacent to o}| − 1)1(o is in the core)]Thus, the mass-transport principle implies thatE[|{v in the core : v is adjacent to o}| | o is in the core] = 2.If F has a multiply-ended component with positive probability, then on this event its core isnonempty, and every vertex in the core has at least two other vertices in the core adjacent toit. If F has a component with more than two ends with positive probability, then on this eventthere exists a vertex in the core with at least three vertices in the core adjacent to it, and it fol-lows from automorphism invariance that the origin is such a vertex with positive probability. Thestatement about the expectation above implies that this cannot be the case, and so we deduce thatevery component of the WUSF has at most two ends as claimed.The authors then rule out the existence of a two ended component, considering separatelythe cases that the WUSF is connected or disconnected. The case that the WUSF is connectedis handled by a reasonably straightforward but still very elegant argument, a generalised versionof which appears in [127] (Chapter 4 of this thesis). For the disconnected case, the authors firstshow that if F contains two-ended components, then it is possible to sample F conditioned on theorigin being contained in the trunk of its component by first sampling the trunk, and then runningWilson’s algorithm ‘rooted at the trunk’ to sample the rest of F, i.e., beginning the recursion inWilson’s algorithm by setting F0 to be the trunk. The fact that this works, which the authors callthe trunk lemma, is intuitively plausible but unfortunately rather technical to prove.Once the trunk lemma is in place, we come to Schramm’s “smoke and mirrors” mass-transportargument. Suppose for contradiction that F contains a two-ended component with positive proba-391.5. Uniform spanning forestsbility. Since F is disconnected, the trunk lemma implies that, conditional on both the trunk of thetree containing the origin, denoted T , and the event that this trunk contains the origin, there issome vertex w of G such that the random walk started at w does not hit T with positive probability.Let W be the set of such vertices. Then it is not hard to see that W must be adjacent to somevertex of T , and automorphsim-invariance implies that the origin is such a vertex with positiveprobability. it follows that, with positive probability, a random walk started at the origin does notreturn to T after time zero. In notation,E[τ+T 1(o is in the trunk of a two-ended component)]=∞Now, for each vertex v in the trunk of a two-ended component of F, let Bv be the set of verticesu, including v itself, such that any simple infinite path starting at u in F must pass through v,called the bush at v. The trunk lemma implies that the probability that u is in Bo conditional onT and the event o ∈ T is equal to the probability that a random walk started at u hits T , and doesso for the first time at o. By time reversal, this is equal to the expected number of times a randomwalk started at o hits u before returning to T for the first time, and so, summing over u,E[|Bo|1(o in the trunk of a two-ended component)]= E[τ+T 1(o in the trunk of a two-ended component)]=∞On the other hand, if we transport mass from each vertex of u of G in a two-ended component ofF to the unique vertex v such that u ∈ Bv, we obtain from the mass-transport principle thatE|Bo|1(o is in the trunk of a two-ended component) = P(o is in a two-ended component) <∞,giving us the desired contradiction.A more geometric understanding of one-endedness in the transient case was developed byLyons, Morris, and Schramm [170] in 2008. These authors gave an isoperimetric criterion forone-endedness, very similar to the Thomassen criterion for transience. Their proof was based onelectrical techniques; see [173] for an updated exposition.Theorem (Lyons, Morris, and Schramm 2008). Let G be a graph that satisfies an f(t)-isoperimetricinequality for some increasing function f : (0,∞)→ (0,∞) for which there exists a constant α suchthat f(t) ≤ t and f(2t) ≤ αf(t) for all t ∈ (0,∞). If∫ ∞11f(t)2dt <∞,then every component of the wired uniform spanning forest of G is one-ended almost surely.Corollary (Lyons, Morris, and Schramm 2008). Let G be a transitive transient graph. Then everycomponent of the wired uniform spanning forest of G is one-ended almost surely.401.5. Uniform spanning forestsTrees with one end (or finitely many ends) are clearly recurrent by the Nash-Williams Criterion.Recurrence of components in the WUSF holds even more generally than one-endedness, however,as was proven by Morris in 2003 [185] using electrical methods.Theorem (Morris 2003). Let G be an infinite graph. Then every component of the wired uniformspanning forest of G is recurrent almost surely.1.5.6 The interlacement Aldous-Broder algorithmUnlike Wilson’s algorithm, it was for a long time not apparent how to extend the Aldous-Broderalgorithm to generate the wired uniform spanning forest of an infinite transient graph. In ourpaper [128] (Chapter 5 of this thesis), we showed that such an extension can be done by replacingthe random walk in the classical algorithm with the random interlacement process. Theinterlacement Aldous-Broder algorithm turns out, generally speaking, to be better suited thanWilson’s algorithm for studying ends in the WUSF, and allowed us to prove several new results. Itis also of central importance in upcoming work in which we compute the critical exponents for theUSF in high dimensions.The interlacement process was originally introduced by Sznitman [216] to study the disconnec-tion of cylinders and tori by a random walk trajectory, and was generalised to arbitrary transientgraphs by Teixeira [218]. See the monographs [67, 82] for detailed introductions. Roughly speaking,the interlacement process I on a transient graph G is a ‘Poissonian soup’ of bi-infinite randomwalk trajectories in G. As we increase a real time parameter t, more and more of these trajectoriesappear. Formally, I is a random subset of W/ ∼ ×R, where W is the space of doubly infinitepaths in G that visit each vertex at most finitely often, and ∼ holds two such paths to be equivalentif and only if they are reparameterizations of each other.Theorem (H. 2015). Let G be a transient graph, let I be the interlacement process on G, and lett ∈ R. For each vertex v of G, let τt(v) be the smallest time greater than t such that there existsa trajectory (Wτt(v), τt(v)) ∈ I passing through v, and let et(v) be the oriented edge of G that istraversed by the trajectory Wτt(v) as it enters v for the first time. ThenABt(I ) :={−et(v) : v ∈ V }has the law of the oriented wired uniform spanning forest of G.We used this algorithm to prove an anchored isoperimetric condition for one-endedness, an-swering positively a question of Lyons, Morris, and Schramm [170].Theorem (H. 2015). Let G be a graph that satisfies an anchored f(t)-isoperimetric inequality forsome increasing function f : (0,∞)→ (0,∞) for which there exists a constant α such that f(t) ≤ tand f(2t) ≤ αf(t) for all t ∈ (0,∞). Suppose that f also satisfies each of the following conditions:411.5. Uniform spanning forests1. ∫ ∞11f(t)2dt <∞and2. ∫