Κύρια Selected works of Oded Schramm

Selected works of Oded Schramm

, ,

This volume is dedicated to the memory of the late Oded Schramm (1961-2008), distinguished mathematician. Throughout his career, Schramm made profound and beautiful contributions to mathematics that will have a lasting influence.

In these two volumes, Editors Itai Benjamini and Olle Häggström have collected some of his papers, supplemented with three survey papers by Steffen Rohde, Häggström and Cristophe Garban that further elucidate his work. The papers within are a representative collection that shows the breadth, depth, enthusiasm and clarity of his work, with sections on Geometry, Noise Sensitivity, Random Walks and Graph Limits, Percolation, and finally Schramm-Loewner Evolution. An introduction by the Editors and a comprehensive bibliography of Schramm's publications complete the volume. The book will be of especial interest to researchers in probability and geometry, and in the history of these subjects.

Χρόνος: 2011
Έκδοση: 1
Εκδότης: Springer-Verlag New York
Γλώσσα: english
Σελίδες: 1247 / 1244
ISBN 10: 1441996753
ISBN 13: 9781441996756
Series: Selected works in probability and statistics
File: DJVU, 19.84 MB

Most frequently terms

Post a Review You can write a book review and share your experiences. Other readers will always be interested in your opinion of the books you've read. Whether you've loved the book or not, if you give your honest and detailed thoughts then people will find new books that are right for them.
1

Probability demystified

Χρόνος: 2005
Γλώσσα: english
File: PDF, 1.47 MB
2

The computation of Galois groups

Χρόνος: 1981
Γλώσσα: english
File: DJVU, 347 KB
Selected Works in Probability and Statistics For other titles published in this series, go to www.springer.com/series/8556

Itai Benjamini · Olle Haggstrom Editors Selected Works of Oded Schramm Springer

Editors Itai Benjamini Weizmann Institute of Science Department of Mathematics Rehovot 76100, Israel itai. benjamini @ weizmann.ac.il Olle Haggstrom Department of Mathematical Statistics Chalmers University of Technology Goteborg, Sweden olleh @ Chalmers. se e-ISBN 978-1-4419-9675-6 Printed in 2 volumes ISBN 978-1-4419-9674-9 DOI 10.1007/978-1-4419-9675-6 Springer New York Dordrecht Heidelberg London Library of Congress Control Number: 2011931468 © Springer Science+Business Media, LLC 2011 All rights reserved. This work may not be translated or copied in whole or in part without the written permission of the publisher (Springer Science+Business Media, LLC, 233 Spring Street, New York, NY 10013, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed is forbidden. The use in this publication of trade names, trademarks, service marks, and similar terms, even if they are not identified as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary rights. Printed on acid-free paper Springer is part of Springer Science+Business Media (www.springer.com)

Preface to the Series Springer's Selected Works in Probability and Statistics series offers scientists and scholars the opportunity of assembling and commenting upon major classical works in statistics, and honors the work of distinguished scholars in probability and statistics. Each volume contains the original papers, original commentary by experts on the subject's papers, and relevant biographies and bibliographies. Springer is committed to maintaining the volumes in the series with free access of SpringerLink, as well as to the distribution of print volumes. The full text of the volumes is available on SpringerLink with the exception of a small number of articles for which links to their original publisher is included instead. These publishers have graciously agreed to make the articles freely available on their websites. The goal is maximum dissemination of this material. The subjects of the volumes have been selected by an editorial board consisting of Anirban DasGupta, Peter Hall, Jim Pitman, Michael Sorensen, and Jon Wellner. ν

■' \ ч )

Preface Oded Schramm was born on December 10,1961, in Jerusalem, and died at the age of 46 in a climbing accident on Guye Peak, WA, on September 1, 2008. In between, he made profound and beautiful contributions to mathematics that will have a lasting influence. In these two volumes, we have collected some of his papers, supplemented with three survey papers by Steffen Rohde, Olle Haggstrom and Cristophe Garban that further elucidate his work. Despite the seemingly generous size of the collection, spatial considerations neverthelss forced us to omit most of Oded's papers, and the mere fact that all of them are inspiring pieces of work led to some difficult issues on what to include and what to omit. The reader should not view our choices as an attempt to separate his best works from those that are merely great. Rather, we have tried to put together a representative collection that shows the breadth, depth, enthusiasm and clarity of his work. Others may have diverging opinions on what should or should not have been included, but we do hope that Oded himself would not have been too displeased by our choices. The papers we have included speak for themselves; let us just say a few words about how we have organized them into five sections. Oded began his mathematical career as a geometer, making GEOMETRY the natural topic for Section 1. This section opens with Oded's first two papers from his Master's thesis in 1987 under Gil Kalai at the Hebrew University. We then move on to circle packing and conf ormal geometry, including examples of his extraordinarily fruitful collaboration with Zheng-Xu Hu, and end the section with the joint paper with Mario Bonk on embeddings of hyperbolic spaces. Of course geometric aspects permeate also all of the following sections. In fact, Oded once mentioned to one of us that in order to be able to think about a problem he always liked it to have a geometric component. In the mid 1990's, Oded became interested in the topic of probability theory, which dominates Sections 2-5 of this collection. Section 2 deals in particular with the study of NOISE SENSITIVITY, pioneered in a joint paper with Itai Benjamini and Gil Kalai that opens the section. Noise sensitivity turned out to be a rich topic with applications ranging from voting systems to percolation. In the two other papers of this section, the first coauthored with Jeff Steif and the second with Christophe Garban and Gabor Pete, Oded went progressively deeper into noise sensitivity in a percolation setting, arriving at surprisingly detailed insights. In Section 3 we have collected some of Oded's papers on RANDOM WALKS AND GRAPH LIMITS. This includes (i) a paper with Itai Benjamini establishing recurrence of random walks on suitably defined limits of finite planar graphs, (ii) the joint paper with his student Omer Angel on distributional limits of triangulations, (iii) a singly-authored paper on compositions of random transpositions, (iv) a collaboration with Yuval Peres, Scott Sheffield and David Wilson on the remarkably fruitful interplay between the infinity Laplacian and certain board games, and (v) the concise 2008 paper on so called hyperfinite graph limits. One of the probabilistic objects that caught the strongest grip on Oded's imagination was PERCOLATION, which appeared prominently in Section 2 as a major testing ground for noise sensitivity. Papers on other aspects of percolation are collected in Section 4. Here we will see how Oded joined forces with Itai Benjamini, Russ Lyons and Yuval Peres in order to uncover many of the new vii

viii Preface and interesting phenomena that happen when we move beyond the usual setting of percolation in a Euclidean geometry, and instead study what happens on hyperbolic lattices and other nonamenable graph structures. Most of the papers in this section are joint work with (subsets of) this team of coauthors, plus Harry Kesten who joined them in establishing a beautiful result on uniform spanning trees. We end the section on a different note, namely Oded's joint paper with Itai Benjamini and Gil Kalai making progress on the important open problem of determining the order of magnitude of fluctuations of first passage percolation on the Euclidean lattice. Despite strong competition from Oded's other works, there seems to be a consensus view that the most important of all his contributions to mathematics is his discovery and subsequent study of SCHRAMM-LOEWNER EVOLUTION (or stochastic Loewner avolution as Oded himself preferred to call it; conveniently, the abbreviation SLE works either way), which is the topic of Section 5. SLE is a family of conformally invariant random processes in the plane that turn out to appear as the scaling limit of percolation and a variety of other critical models. We begin this section with the famous paper, published in 2000 in the Israel Journal of Mathematics, where Schramm singlehandedly discovered SLE and obtained the first preliminary results on scaling limits. Then followed a series of papers with Greg Lawler and Wendelin Werner in which SLE was exploited to deduce deep results on intersection properties of random walks; here we include only some of the highlights. We furthermore include important joint papers with Steffen Rohde, Scott Sheffield, David Wilson and Stanislav Smirnov, plus Oded's contribution to the International Congress of Mathematicians in Madrid, 2006, in which he gives a survey of the field with an emphasis on open problems. There were no signs of a decrease in creativity or productivity on Oded's part until the untimely and tragic end, and we can only guess what further discoveries we miss because of it. Substantial parts of his work, joint with others, is still not completely written up and will appear in the coming years. However, Oded will be missed not just because of his mathematics, but even more because of the gentle, warm-hearted and generous person that he was. Of course, the loss of him is felt most strongly by his wife Avivit, his daughter Tselil and his son Pele. But he was very much loved by the mathematical community and by everyone who knew him, as amply witnessed on the memorial blog which was setup shortly after his death: http://odedschramm.wordpress.com/ We hope that this collection will contribute, however modestly, to keeping the memory of Oded alive, and to nourishing the mathematical heritage he left for all of us. Yehi zichro baruch - may the memory of him be a blessing. Itai Benjamini Olle Haggstrom

Acknowledgements This series of selected works is possible only because of the efforts and cooperation of many people, societies, and publishers. The series editors originated the series and directed its development The volume editors spent a great deal of time organizing the volumes and compiling the previously published material. The contributors provided comments on the significance of the papers. The societies and publishers who own the copyright to the original material made the volumes possible and affordable by their generous cooperation: American Institute of Mathematical Sciences American Mathematical Society Duke University Press Hebrew University Magnes Press Institute of Mathematical Statistics Institute of Mathematical Studies bistitut des Hautes Etudes Scientifiques International Mathematical Union The London Mathematical Society Princeton University and the Institute for Advanced Studies Springer Science+Business Media Yuval Peres ix

Contents Volume 1 Part 1: Geometry Commentary: Oded Schramm: From circle packing to SLE, by Steffen Rohde· To appear in Ann. Probab. Reprinted with permission of the Institute of Mathematical Statistics 3 O· Schramm· Illuminating sets of constant width· Mathematika Vol. 35 No· 2,180-189 (1988)· Reprinted with permission of The London Mathematical Society 47 O· Schramm· On the volume of sets having constant width. Israel J. Math. Vol· 63 No· 2, 178-182 (1988)· Reprinted with permission of Hebrew University Magnes Press 57 O· Schramm· Rigidity of infinite (circle) packings. / Amer. Math. Soc. Vol· 4 No· 1, 127-149 (1991)· Reprinted with permission of the American Mathematical Society 63 O· Schramm· How to cage an egg· Invent Math. Vol· 107 No· 3, 543-560 (1992)· Reprinted with permission of Springer Science+Business Media 87 Zheng-Xu He and O· Schramm· Fixed points, Koebe uniformization and circle packings· Ann. of Math. (2) Vol· 137 No· 2, 369-406 (1993)· Reprinted with permission of Princeton University and the Institute for Advanced Study 105 Zheng-Xu He and O· Schramm· Hyperbolic and parabolic packings· Discrete Comput. Geom. Vol· 14 No· 2,123-149 (1995)· Reprinted with permission of Springer Science+Business Media 143 O· Schramm· Circle patterns with the combinatorics of the square grid· Duke Math. J. Vol· 86 No· 2, 347-389 (1997)· Reprinted with permission of Duke University Press· An electronic version is available at doi: 10.1215/S0012-7094-97-08611-7 171 Zheng-Xu He and O· Schramm· The Coo-convergence of hexagonal disk packings to the Riemann map. Acta Math. Vol· 180 No· 2, 219-245 (1998)· Reprinted with permission of Springer Science+Business Media 215 M· Bonk and O· Schramm· Embeddings of Gromov hyperbolic spaces. Geom. Funct. Anal. Vol· 10 No· 2, 266-306 (2000)· Reprinted with permission of Springer Science+Business Media 243 xi

xii Contents Part 2: Noise Sensitivity Commentary: Oded Schramm's contributions to noise sensitivity, by Christophe Garban· To appear in Ann. Probab. Reprinted with permission of the Institute of Mathematical Statistics 287 L Benjamini, G· Kalai, and O· Schramm· Noise sensitivity of Boolean functions and applications to percolation. Inst. Hautes Etudes Sci. PubL Math. No· 90,5-43 (1999)· Reprinted with permission of Institut Des Hautes Etudes Scientifiques 351 O· Schramm and J· E· Steif· Quantitative noise sensitivity and exceptional times for percolation· Annals of Mathematics, Pages 619-672 from Volume 171 (2010), Issue 2· Reprinted with permission of Princeton University and the Institute for Advanced Study 391 C· Garban, G· Pete, and O· Schramm· The Fourier spectrum of critical percolation· Acta Math. 205 (2010), 19-104· Reprinted with permission of Springer Science^Business Media 445 Part 3: Random Walks and Graph Limits L Benjamini and O· Schramm· Recurrence of distributional limits of finite planar graphs· Electron J. Probab. Vol· 6, No· 23,13 pp· (electronic) (2001)· Reprinted with permission of the Institute of Mathematical Statistics 533 O· Angel and O· Schramm· Uniform infinite planar triangulations. Comm. Math. Phys. Vol· 241 No· 2-3, 191-213 (2003)· Reprinted with permission of Springer Science^Business Media 547 O· Schramm· Compositions of random transpositions· Israel J. Math. Vol· 147,221-243 (2005)· Reprinted with permission of Hebrew University Magnes Press 571 Y· Peres, O· Schramm, S· Sheffield, and D· B· Wilson· Thg-of-war and the infinity Laplacian· Journal of the American Mathematical Society 22(1): 167-210, (2009)· Reprinted with permission of Yuval Peres 595 O· Schramm· Hyperfinite graph limits· Electron. Res. Announc. Math. Sci. Vol· 15, 17-23 (2008)· Reprinted with permission of the American Institute of Mathematical Sciences 639 Volume 2 Part 4: Percolation Commentary: Percolation beyond Zd: The contributions of Oded Schramm, by Olle Haggstrom· To appear in Ann. Probab. Reprinted with permission of the Institute of Mathematical Statistics 649 L Benjamini and O· Schramm· Percolation beyond Zd, many questions and a few answers· Electron. Comm. Probab. Vol· 1, No· 8, 71-82 (electronic) (1996)· Reprinted with permission of the Institute of Mathematical Statistics 679 L Benjamini, R· Lyons, Y· Peres, and O· Schramm· Critical percolation on any nonamenable group has no infinite clusters· Ann. Probab. Vol· 27 No· 3,1347-1356 (1999)· Reprinted with permission of the Institute of Mathematical Statistics 691

Contents Xlll R. Lyons and O. Schramm· Indistinguishability of percolation clusters. Ann. Probab. Vol. 27 No. 4, 1809-1836 (1999). Reprinted with permission of the Institute of Mathematical Statistics 701 L Benjamini and O. Schramm. Percolation in the hyperbolic plane. /. Amer. Math. Soc. Vol. 14 No. 2, 487-507 (electronic) (2001). Reprinted with permission of the American Mathematical Society 729 I. Benjamini, H. Kesten, Y. Peres, and O. Schramm. Geometry of the uniform spanning forest: transitions in dimensions 4, 8,12,... Ann. of Math. (2) Vol. 160 No. 2, 465-491 (2004). Reprinted with permission of Princeton University and the Institute for Advanced Study 751 I. Benjamini, G. Kalai, and O. Schramm. First passage percolation has sublinear distance variance. Ann. Probab. Vol. 31 No. 4, 1970-1978 (2003). Reprinted with permission of the Institute of Mathematical Statistics 779 Part 5: Schramm-Loewner Evolution O. Schramm. Scaling limits of loop-erased random walks and uniform spanning trees. Israel J. Math. Vol. 118, 221-288 (2000). Reprinted with permission of Hebrew University Magnes Press 791 G. F. Lawler, O. Schramm, and W. Werner. Values of Brownian intersection exponents I: Half-plane exponents. Acta Math. Vol. 187 No. 2, 237-273 (2001). Reprinted with permission of Springer Science+Business Media 859 G. F. Lawler, O. Schramm, and W. Werner. Values of Brownian intersection exponents II: Plane exponents. Acta Math. Vol. 187 No. 2, 275-308 (2001). Reprinted with permission of Springer Science+Business Media 897 G. F. Lawler, O. Schramm, and W. Werner. Conformal invariance of planar loop-erased random walks and uniform spanning trees. Ann. Probab. Vol. 32 No. IB, 939-995 (2004). Reprinted with permission of the Institute of Mathematical Statistics 931 S. Rohde and O. Schramm. Basic properties of SLE. Ann. of Math. (2) Vol. 161 No. 2, 883-924 (2005). Reprinted with permission of Princeton University and the Institute for Advanced Study 989 O. Schramm and S. Sheffield. Contour lines of the two-dimensional discrete Gaussian free field. Acta Mathematical Vol. 202 No. 1,21-137 (2009). Reprinted with permission of Springer Science+Business Media 1031 O. Schramm, S. Sheffield, and D. B. Wilson. Conformal radii for conformal loop ensembles. Commun.Math.Phys.2SS: 43-53, (2009). Reprinted with permission of Springer Science+Business Media 1149 O. Schramm. Conformally invariant scaling limits: an overview and a collection of problems. In International Congress of Mathematicians. Vol. I, 513-543, Eur. Math. Soc, Zurich (2007). Reprinted with permission of the International Mathematical Union 1161 O. Schramm and S. Smirnov. On the scaling limits of planar percolation. To appear in Ann. Probab. Reprinted with permission of the Institute of Mathematical Statistics 1193

Contributors Itai Benjamini The Weizmann Institute of Science, Rehovot РОВ 76100, Israel, itai.benjamini@weizmann.ac.il Cristophe Garban Departement de mathematiques, CNRS, 46, allee d'ltalie, 69364 Lyon Cedex 07, France, christophe.garban@ umpa.ens-lyon.fr Olle Haggstrom Mathematical Sciences, Chalmers University of Technology, 412 96 Goteborg, Sweden, olleh@chalmers.se Steffen Rohde University of Washington, Department of Mathematics, C-337 Padelford Hall, Box 354350 Seattle, WA 98195-4350, United States, rohde@math.washington.edu xv

Author Bibliography Oded Schramm's publications, as of January 2011 *0. Schramm. Illuminating sets of constant width. Mathematika Vol. 35 No. 2, 180-189 (1988). *0. Schramm. On the volume of sets having constant width. Israel J, Math, Vol. 63 No. 2, 178-182 (1988). O. Schramm. Packing two dimensional bodies with prescribed combinatorics and applications to the construction of conformal and quasiconformal mappings. Ph. D. thesis. Princeton University (1990). *0. Schramm. Rigidity of infinite (circle) packings. /. Amer, Math, Soc, Vol. 4 No. 1,127-149 (1991). O. Schramm. Existence and uniqueness of packings with specified combinatorics. Israel J, Math, Vol. 73 No. 3, 321-341 (1991). *0. Schramm. How to cage an egg. Invent, Math, Vol. 107 No. 3, 543-560 (1992). O. Schramm. Square tilings with prescribed combinatorics. Israel J, Math, Vol. 84 No. 1-2, 97-118 (1993). *Zheng-Xu He and O. Schramm. Fixed points, Koebe uniformization and circle packings. Ann, of Math, (2) Vol. 137 No. 2, 369^06 (1993). G. Kuperberg and O. Schramm. Average kissing numbers for non-congruent sphere packings. Math, Res, Lett, Vol. 1 No. 3, 339-344 (1994). Zheng-Xu He and O. Schramm. Rigidity of circle domains whose boundary has σ-finite linear measure. Invent, Math, Vol. 115 No. 2, 297-310 (1994). Zheng-Xu He and O. Schramm. Koebe uniformization for "almost circle domains". Amer, J, Math, Vol. 117 No. 3, 653-667 (1995). *Zheng-Xu He and O. Schramm. Hyperbolic and parabolic packings. Discrete Comput, Geom, Vol. 14 No. 2, 123-149 (1995). Zheng-Xu He and O. Schramm. The inverse Riemann mapping theorem for relative circle domains. Pacific J, Math, Vol. 171 No. 1, 157-165 (1995). O. Schramm. Transboundary extremal length. J, Anal, Math, Vol. 66, 307-329 (1995). O. Schramm. Conformal uniformization and packings. Israel J, Math, Vol. 93, 399^-28 (1996). Z. Reich, O. Schramm, V Brumfeld, and A. Minsky. Chiral discrimination in DNA-peptide interactions involving chiral DNA mesophases: a geometric analysis. Jour, Amer, Chem, Soc, Vol. 118, 6345-6349 (1996). Zheng-Xu He and O. Schramm. On the convergence of circle packings to the Riemann map. Invent, Math, Vol. 125 No. 2, 285-305 (1996). * Indicates article found in Vol. 1 + Indicates article found in Vol.2 xvii

xviii Author Bibliography +L Benjamini and O. Schramm. Percolation beyond Zd, many questions and a few answers. Electron, Comm, Probab, Vol. 1, No. 8, 71-82 (electronic) (1996). I. Benjamini and O. Schramm. Harmonic functions on planar and almost planar graphs and manifolds, via circle packings. Invent Math, Vol. 126 No. 3, 565-587 (1996). I. Benjamini and O. Schramm. Random walks and harmonic functions on infinite planar graphs using square tilings. Ann, Probab, Vol. 24 No. 3, 1219-1238 (1996). *0. Schramm. Circle patterns with the combinatorics of the square grid. Duke Math, J, Vol. 86 No. 2, 347-389 (1997). I. Benjamini and O. Schramm. Every graph with a positive Cheeger constant contains a tree with a positive Cheeger constant Geom, Funct, Anal, Vol. 7 No. 3, 403^-19 (1997). Zheng-Xu He and O. Schramm. On the distortion of relative circle domain isomorphisms. /. Anal, Math, Vol. 73, 115-131 (1997). *Zheng-Xu He and O. Schramm. The Coo-convergence of hexagonal disk packings to the Riemann map. Acta Math, Vol. 180 No. 2, 219-245 (1998). I. Benjamini and O. Schramm. Exceptional planes of percolation. Probab, Theory Related Fields Vol. Ill No. 4, 551-564 (1998). I. Benjamini and O. Schramm. Conformal invariance of Voronoi percolation. Comm, Math, Phys, Vol. 197 No. 1,75-107 (1998). I. Benjamini and O. Schramm. Recent progress on percolation beyond Zd. (1998). revised Jan 18 2000 [Web paper] I. Benjamini, R. Lyons, Y. Peres, and O. Schramm. Group-invariant percolation on graphs. Geom, Funct, Anal, Vol. 9 No. 1, 29-66 (1999). R. Lyons and O. Schramm. Stationary measures for random walks in a random environment with random scenery. New York J, Math, Vol. 5, 107-113 (electronic) (1999). 0. Schramm and B. Tsirelson. Trees, not cubes: hypercontractivity, cosiness, and noise stability. Electron, Comm, Probab, Vol. 4, 39^9 (electronic) (1999). +I. Benjamini, R. Lyons, Y. Peres, and O. Schramm. Critical percolation on any nonamenable group has no infinite clusters. Ann, Probab, Vol. 27 No. 3, 1347-1356 (1999). 1. Benjamini, R. Lyons, and O. Schramm. Percolation perturbations in potential theory and random walks. In Random walks and discrete potential theory (Cortona, 1997), Sympos. Math., XXXIX, 56-84, Cambridge Univ. Press, Cambridge (1999). +R. Lyons and O. Schramm. Indistinguishability of percolation clusters. Ann, Probab, Vol. 27 No. 4, 1809-1836(1999). *L Benjamini, G. Kalai, and O. Schramm. Noise sensitivity of Boolean functions and applications to percolation Inst, Routes Etudes Set, Publ, Math, No. 90, 5^-3 (1999). I. Benjamini, O. Haggstrom, and O. Schramm. On the effect of adding ε-Bernoulli percolation to everywhere percolating subgraphs of Zd. /. Math, Phys, Vol. 41 No. 3, 1294-1297 (2000). *M. Bonk and O. Schramm. Embeddings of Gromov hyperbolic spaces. Geom, Funct, Anal, Vol. 10 No. 2, 266-306 (2000). +0. Schramm. Scaling limits of loop-erased random walks and uniform spanning trees. Israel J, Math, Vol. 118, 221-288 (2000). J. Jonasson and O. Schramm. On the cover time of planar graphs. Electron, Comm, Probab, Vol. 5, 85-90 (electronic) (2000). +I. Benjamini and O. Schramm. Percolation in the hyperbolic plane. /. Amer, Math, Soc, Vol. 14 No. 2, 487-507 (electronic) (2001). I. Benjamini, R. Lyons, Υ Peres, and O. Schramm. Uniform spanning forests. Ann, Probab, Vol. 29 No. 1, 1-65 (2001). +G.F. Lawler, O. Schramm, and W. Werner. Values of Brownian intersection exponents I: Half-plane exponents. Acta Math, Vol. 187 No. 2, 237-273 (2001).

Author Bibliography xix +G.F. Lawler, O. Schramm, and W. Werner. Values of Brownian intersection exponents II: Plane exponents. Acta Math, Vol. 187 No. 2, 275-308 (2001). G.F. Lawler, O. Schramm, and W. Werner. The dimension of the planar Brownian frontier is 4/3. Math, Res, Lett, Vol. 8 No. 4, 401^11 (2001). *L Benjamini and O. Schramm. Recurrence of distributional limits of finite planar graphs. Electron, J, Probab, Vol. 6, No. 23, 13 pp. (electronic) (2001). 0. Schramm. A percolation formula. Electron, Comm, Probab, Vol. 6, 115-120 (electronic) (2001). G.F. Lawler, O. Schramm, and W. Werner. Values of Brownian intersection exponents III: Two-sided exponents. Ann, Inst, H, Poincare Probab, Statist, Vol. 38 No. 1, 109-123 (2002). G.F. Lawler, O. Schramm, and W. Werner. Analyticity of intersection exponents for planar Brownian motion. Acta Math, Vol. 189 No. 2, 179-201 (2002). G.F. Lawler, O. Schramm, and W. Werner. Sharp estimates for Brownian non-intersection probabilities. In In and out ofequilibnum (Mambucaba, 2000), Progr. Probab. Vol. 51,113-131, Birkhauser Boston, Boston, MA (2002). G.F. Lawler, O. Schramm, and W. Werner. One-arm exponent for critical 2D percolation Electron. /. Probab, Vol. 7, No. 2, 13 pp. (electronic) (2002). R. Lyons, Y. Peres, and O. Schramm. Markov chain intersections and the loop-erased walk Aww. Inst, H, Poincare Probab, Statist, Vol. 39 No. 5, 779-791 (2003). +I. Benjamini, G. Kalai, and O. Schramm. First passage percolation has sublinear distance variance. Ann, Probab, Vol. 31 No. 4, 1970-1978 (2003). *0. Angel and O. Schramm. Uniform infinite planar triangulations. Comm, Math, Phys, Vol. 241 No. 2-3, 191-213 (2003). G.F. Lawler, O. Schramm, and W. Werner. Conformal restriction: the chordal case. /. Amer, Math, Soc, Vol. 16 No. 4, 917-955 (electronic) (2003). +I. Benjamini, H. Kesten, Y. Peres, and O. Schramm. Geometry of the uniform spanning forest: transitions in dimensions 4, 8, 12,... Ann, of Math, (2) Vol. 160 No. 2, 465^91 (2004). +G.F. Lawler, O. Schramm, and W. Werner. Conformal invariance of planar loop-erased random walks and uniform spanning trees. Ann, Probab, Vol. 32 No. IB, 939-995 (2004). G.F. Lawler, O. Schramm, and W. Werner. On the scaling limit of planar self-avoiding walk. ^Fractal geometry and applications: a jubilee of Benott Mandelbrot, Part 2, Proc, Sympos, Pure Math, Vol, 72, 339-364, Amer, Math, Soc, Providence, RI (2004). 1. Benjamini, S. Merenkov, and O. Schramm. A negative answer to Nevanlinna's type question and a parabolic surface with a lot of negative curvature. Proc, Amer, Math, Soc, Vol. 132 No. 3, 641-647 (electronic) (2004). I. Benjamini and O. Schramm. Pinched exponential volume growth implies an infinite dimensional isoperimetric inequality. In Geometnc aspects of functional analysis, Lecture Notes in Math, Vol. 1850, 73-76, Springer, Berlin (2004). +S. Rohde and O. Schramm. Basic properties of SLE. Ann, of Math, (2) Vol. 161 No. 2, 883-924 (2005). 0. Schramm and S. Sheffield. Harmonic explorer and its convergence to SLE(4). Ann, Probab, Vol. 33 No. 6, 2127-2148 (2005). *0. Schramm. Compositions of random transpositions. Israel J, Math, Vol. 147, 221-243 (2005). 1. Benjamini, O. Schramm, and D.B.Wilson. Balanced Boolean functions that can be evaluated so that every input bit is unlikely to be read. In STOC'05: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 244-250, ACM, New York (2005). O. Schramm. Emergence of Symmetry: Conformal invariance in scaling limits of random systems. In European congress of mathematics (ECM), Stockholm, Sweden, June 27-July 2, 2004, Ari Laptev editor, 783-786, European Mathematical Society, Zurich (2005). O. Schramm and D.B. Wilson. SLE coordinate changes. New York J, Math, Vol. 11:659-669, (2005).

XX Author Bibliography R. O'Donnell, M. Saks, O. Schramm, and R. Servedio. Every decision tree has an influential variable. In Proceedings of the 46th Annual Symposium on Foundations of Computer Science (FOCS) (2005). A. Naor, Y. Peres, O. Schramm, and S. Sheffield. Markov chains in smooth Banach spaces and Gromov-hyperbolic metric spaces. Duke Math, J, Vol. 134 No. 1,165-197 (2006). R. Lyons, Y. Peres, and O. Schramm. Minimal spanning forests. Ann, Probab, Vol. 34 No. 5, 1665- 1692 (2006). Υ Peres, O. Schramm, S. Sheffield, and D.B. Wilson. Random-turn hex and other selection games. Amer, Math, Monthly-Vol. 114 No. 5, 373-387 (2007). +0. Schramm. Conformally invariant scaling limits: an overview and a collection of problems. In International Congress of Mathematicians, Vol. I, 513-543, Eur. Math. Soc, Zurich (2007). R. Lyons, B.J. Morris, and O. Schramm. Ends in uniform spanning forests. Electron, J, Probab, 13 Paper 58 (2008), 1701-1725. R. Lyons, R. Peled, and O. Schramm. Growth of the number of spanning trees of the Erdos-Renyi giant component. Combinatoncs, Probability and Computing,Yolumc 17 Issue 5,711-726, (2008). I. Benjamini, O. Schramm, and A. Shapira. Every minor-closed property of sparse graphs is testable. Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada. *0. Schramm. Hyperfinite graph limits. Electron, Res, Announc, Math, Sci, Vol. 15, 17-23 (2008). *Y Peres, O. Schramm, S. Sheffield, and D.B. Wilson. Tug-of-war and the infinity Laplacian. Journal of the Amencan Mathematical Society 22(1): 167-210, (2009). +0. Schramm and S. Sheffield. Contour lines of the two-dimensional discrete Gaussian free field. Acta Mathematica, Volume 202, Number 1, 21-137, (2009). +0. Schramm, S. Sheffield, and D.B. Wilson. Conformal radii for conformal loop ensembles Com- mun,Math,Phys, 288:43-53, (2009). Υ Peres, O. Schramm, and J.E. Steif. Dynamical sensitivity of the infinite cluster in critical percolation. Ann, Inst, H, Poincare Probab, Statist, Volume 45, Number 2 (2009), 491-514. 0. Schramm and W. Zhou. Boundary proximity of SLE. Probability Theory and Related Fields Volume 146, Numbers Ъ-Ау 435^50, (2009). A.E. Holroyd, R. Pemantle, Υ Peres, and O. Schramm. Poisson matching. Ann, Inst, Henn Poincare Probab, Stat,, 45(1):266-287, (2009). *C. Garban, G. Pete, and O. Schramm. The Fourier spectrum of critical percolation. Acta Math, 205 (2010), 19-104. 1. Benjamini and O. Schramm. KPZ in one dimensional random geometry of multiplicative cascades. Commun, Math, Phys, 289:46-56 (2009). I. Benjamini, J. Jonasson, O. Schramm, and J. Tykesson.Visibility to infinity in the hyperbolic plane, despite obstacles. ALEA Lat, Am, J, Probab, Math, Stat,, Vol. 6 232-343 (2009). *0. Schramm and J.E. Steif. Quantitative noise sensitivity and exceptional times for percolation. Annals of Mathematics, Pages 619-672 from Volume 171 (2010), Issue 2. C. Garban, G. Pete, and O. Schramm. The scaling limit of the minimal spanning tree - a preliminary report. XVIth International Congress on Mathematical Physics (Prague, 2009), ed. P. Exner, pp. 475^80., World Scientific, Singapore, 2010. I. Benjamini, O. Schramm, and S. Sodin. Poisson asymptotics for random projections of points on a high-dimensional sphere. Israel J, Math,, to appear. +0. Schramm and S. Smirnov. On the scaling limits of planar percolation. Ann, Probab,, to appear. C. Garban, S. Rohde, and O. Schramm. Continuity of the SLE trace in simply connected domains. arXiv: 0810.4327 I. Benjamini, O. Gurel-Gurevich, O. Schramm. Cutpoints and resistance of random walk paths. Ann, Probab,, to appear.

Author Bibliography xxi L Benjamini and O. Schramm. Lack of sphere packing of graphs via non-linear potential theory. Jour, of Topology and Analysis, to appear. N. Berestycki, O. Schramm, and O. Zeitouni. Mixing times for random k-cycles and coalescence- fragmentation chains. Arm, Probab,, to appear. I. Benjamini, O. Schramm, and A. Timar. Separation. Groups, Geometry and Dynamics, to appear. C. Garban, G. Pete, and O. Schramm. Pivotal, cluster and interface measures for critical planar percolation. arXiv: 1008.137 8 O. Schramm and S. Sheffield. A contour line of the continuum Gaussian free field. arXiv: 1008.2447

Parti Geometry

Oded Schramm: From Circle Packing to SLE Steffen Rohde* July 12, 2010 Contents 1 Introduction 2 2 Circle Packing and the Koebe Conjecture 3 2.1 Background 3 2.2 Why are Circle Packings interesting? 5 2.3 Existence of Packings 7 2.4 Uniqueness of Packings 9 2.4.1 Extremal length and the conformal modulus of a quadrilateral 10 2.4.2 The Incompatibility Theorem 11 2.4.3 A simple uniqueness proof 13 2.5 Koebe's Kreisnormierungsproblem 13 2.6 Convergence to conformal maps 14 2.7 Other topics 16 3 The Schramm-Loewner Evolution 18 3.1 Pre-history 18 3.2 Definition of SLE 19 3.2.1 The (radial) Loewner equation 19 3.2.2 The scaling limit of LERW 21 3.2.3 The chordal Loewner equation, percolation, and the UST 23 3.3 Properties and applications of SLE 25 3.3.1 Locality 25 3.3.2 Intersection exponents and dimensions 27 3.3.3 Path properties 29 3.3.4 Discrete processes converging to SLE 31 3.3.5 Restriction measures 33 3.3.6 Other results 35 3.4 Problems 36 3.5 Conclusion 37 *University of Washington, Supported in part by NSF Grant DMS-0800968. 1 I. Benjamini, O. Haggstrom (eds.), Selected Works of Oded Schramm, Selected Works in Probability and Statistics, DOI 10.1007/978-l-4419-9675-6_l, © Springer Science+Business Media, LLC 2011 3

1 Introduction When I first met Oded Schramm in January 1991 at the University of California, San Diego, he introduced himself as a "Circle Packer". This modest description referred to his Ph.D. thesis around the Koebe-Andreev-Thurston theorem and a discrete version of the Riemann mapping theorem, explained below. In a series of highly original papers, some joint with Zhen-Xu He, he created powerful new tools out of thin air, and provided the field with elegant new ideas. At the time of his deadly accident on September 1st, 2008, he was widely considered as one of the most innovative and influential probabilists of his time. Undoubtedly, he is best known for his invention of what is now called the Schramm-Loewner Evolution (SLE), and for his subsequent collaboration with Greg Lawler and Wendelin Werner that led to such celebrated results as a determination of the intersection exponents of two-dimensional Brownian motion and a proof of Mandelbrot's conjecture about the Hausdorff dimension of the Brownian frontier. But already his previous work bears witness to the brilliance of his mind, and many of his early papers contain both deep and beautifully simple ideas that deserve better knowing. In this note, I will describe some highlights of his work in circle packings and the Koebe conjecture, as well as on SLE. As Oded has co-authored close to 20 papers related to circle packings and more than 20 papers involving SLE, only a fraction can be discussed in detail here. The transition from circle packing to SLE was through a long sequence of influential papers concerning probability on graphs, many of them written jointly with Itai Benjamini. I will present almost no work from that period (some of these results are described elsewhere in this volume, for instance in Christophe Garban's article on Noise Sensitivity). In that respect, the title of this note is perhaps misleading. In order to avoid getting lost in technicalities, arguments will be sketched at best, and often ideas of proofs will be illustrated by analogies only. In an attempt to present the evolution of Oded's mathematics, I will describe his work in essentially chronological order. Oded was a truly exceptional person: not only was his clear and innovative way of thinking an inspiration to everyone who knew him, but also his caring, modest and relaxed attitude generated a comfortable atmosphere. As inappropriate as it might be, I have included some personal anecdotes as well as a few quotes from email exchanges with Oded, in order to at least hint at these sides of Oded that are not visible in the published literature. This note is not meant to be an overview article about circle packings or SLE. My prime concern is to give a somewhat self-contained account of Oded's contributions. Since SLE has been featured in several excellent articles and even a book, but most of Oded's work on circle packing is accessible only through his original papers, the first part is a bit more expository and contains more background. The expert in either field will find nothing new, and will find a very incomplete list of references. My apology to everyone whose contribution is either unmentioned or, perhaps even worse, mentioned without proper reference. Acknowledgement: I would like to thank Mario Bonk, Jose Fernandez, Jim Gill, Joan Lind, Don Marshall, Wendelin Werner and Michel Zinsmeister for helpful comments on a first draft. I would also like to thank Andrey Mishchenko for generating Figure 3, and Don Marshall for Figure 6. 2 4

2 Circle Packing and the Koebe Conjecture Oded Schramm was able to create, seemingly without effort, ingenious new ideas and methods. Indeed, he would be more likely to invent a new approach than to search the literature for an existing one. In this way, in addition to proving wonderful new theorems, he rediscovered many known results, often with completely new proofs. We will see many examples throughout this note. Oded received his Ph.D. in 1990 under William Thurston's direction at Princeton. His thesis, and the majority of his work until the mid 90's, was concerned with the fascinating topic of circle packings. Let us begin with some background and a very brief overview of some highlights of this field prior to Oded's thesis. Other surveys are [Sa] and [Ste2]. 2.1 Background According to the Riemann mapping theorem, every simply connected planar domain, except the plane itself, is conformally equivalent to a disc. The conformal map to the disc is unique, up to postcomposition with an automorphism of the disc (which is a Mobius transformation). The standard proof exhibits the map as a solution of an extremal problem (among all maps of the domain into the disc, maximize the derivative at a given point). The situation is quite different for multiply connected domains, partly due to the lack of a standard target domain. The standard proof can be modified to yield a conformal map onto a parallel slit domain (each complementary component is a horizontal line segment or a point). Koebe showed that every finitely connected domain is conformally equivalent to a circle domain (every boundary component is a circle or a point), in an essentially unique way. No proof similar to the standard proof of the Riemann mapping theorem is known. Theorem 2.1 ([Kol]). For every domain Ω С С with finitely many connected boundary components, there is a conformal map f onto a domain il'cC all of whose boundary components are circles or points. Both f and Ω' are unique up to a Mobius transformation. Koebe conjectured (p. 358 of [Kol]) that the same is true for infinitely connected domains. It later turned out that uniqueness of the circle domain can fail (for instance, it fails whenever the set of point-components of the boundary has positive area, as a simple application of the measurable Riemann mapping theorem shows). But existence of a conformally equivalent circle domain is still open, and is known as Koebe's conjecture or "Kreisnormierungsproblem". It motivated a lot of Oded's research. There is a close connection between Koebe's theorem and circle packings. A circle packing Ρ is a collection (finite or infinite) of closed discs D in the two dimensional plane C, or in the two dimensional sphere 52, with disjoint interiors. Associated with a circle packing is its tangency graph or nerve G = (V,E), whose vertices correspond to the discs, and such that two vertices are joined by an edge if and only if the corresponding discs are tangent. We will only consider packings whose tangency graph is connected. Conversely, the Koebe-Andreev-Thurston Circle Packing Theorem guarantees the existence of packings with prescribed combinatorics. Loosely speaking, a planar graph is a graph that can be drawn in the plane so that edges do not cross. Our graphs will not have double edges (two edges with the same endpoints) or loops (an edge whose endpoints coincide). 3 5

Figure 1: A circle packing and its tangency graph. Theorem 2.2 ([Ko2], [T], [Al]). For every finite planar graph G, there is a circle packing in the plane with nerve G. The packing is unique (up to Mobius transformations) if G is a triangulation ofS2. See the following sections for the history of this theorem, and sketches of proofs. In particular, in Section 2.3 we will indicate how the Circle Packing Theorem 2.2 can be obtained from the Koebe Theorem 2.1, and conversely that the Koebe theorem can be deduced from the Circle Packing Theorem. Every finite planar graph can be extended (by adding vertices and edges as in Figure 3(c)) to a triangulation, hence packability of triangulations implies packability of finite planar graphs (there are many ways to extend a graph to a triangulation, and uniqueness of the packing is no longer true). The situation is more complicated for infinite graphs. Oded wrote several papers dealing with this case. Thurston conjectured that circle packings approximate conformal maps, in the following sense: Consider the hexagonal packing Ηε of circles of radius ε (a portion is visible in Fig. 2 and Fig. 3(a)). Let Ω С С be a domain (a connected open set). Approximate Ω from the inside by a circle packing P€ of circles of Ω Π Ηει as in Fig. 2 and Fig. 3(a) (more precisely, take the connected component containing ρ of the union of those circles whose six neighbors are still contained in Ω). Complete the nerve of this packing by adding one vertex for each connected component of the complement to obtain a triangulation of the sphere (there are three new vertices v\,V2,V3 in Fig. 3(c); the three copies of v\$ are to be identified). By the Circle Packing Theorem, there is a circle packing P'e of the sphere with the same tangency graph (Figures 2 and 3(d) show these packings after stereographic projection from the sphere onto the plane; the circle corresponding to V3 was chosen as the upper hemisphere and became the outside of the large circle after projection). Notice that each of the complementary components now corresponds to one ("large") circle of Ρε, and the circles in the boundary of Ρε are tangent to these complementary circles. Now consider the map fe that sends the centers of the circles of Ρε to the corresponding centers in P^ and extend it in a piecewise linear fashion. Rodin and Sullivan proved Thurston's conjecture that f€ approximates 4 6

Figure 2: Λ circle packing approximation to a Riemann map. the Riemann map, if Ω is simply connected (sec Fig. 2): Theorem 2.3. (RSuJ Let Ω be simply connected, ρ,ηζΩ, and F* normalized such that the complementary circle is the unit circle, and such that the circle closest to ρ (resp. q) corresponds to a circle containing 0 (resp. some positive real number). Then the above maps fe converge to the conjormal map f : Ω -» D that is normalized by f(p) = 0 and f(q) > 0, uniformly on compact subeets of Ω as ε -»0. Their proof depends crucially on the non-trivial uniqueness of the hexagonal packing as the only packing in the plane with nerve the triangular lattice. Odcd found remarkable improvements and generalizations of this theorem. See Section 2.6 for further discussion. 2.2 Why are Circle Packings interesting? Despite their intrinsic beauty (sec the book [Ste2] for stunning illustrations and an elementary introduction), circle packings are interesting because they provide a canonical and conformally natural way to embed a planar graph into a surface. Thus they have applications to combinatorics (for instance the proof of Miller and Thurston (MTj of the Lipton-Tarjan separator theorem, sec e.g. the slides of Odcd's circle packing talk on his memorial webpage), to differential geometry (for instance the construction of minimal surfaces by Bobcnko, Hoffmann and Springborn [BUS] and their references), to geometric analysis (for instance, the Honk-Kleiner [BK] quasisyminetric parainctrization of Ahlfors 2-regular LLC topological spheres) to discrete probability theory (for instance, through the work of Benjamini and Schramm on harmonic functions on graphs and recurrence on random planar graphs [BS1],[BS2], [BS3]) and of course to complex analysis (discrete analytic functions, conforms! mapping). However, Odcd's work on circle packing did not follow any "main-stream" in conforms! geometry or geometric function theory. I believe he continued to work on tliem just because he liked it. His interest never wavered, and many of his numerous late contributions to Wikipcdia were about this topic. Existence and uniqueness arc intimately connected. Nevertheless, for better readability I will discuss them in two separate sections. 5

(a) (b) (с) (d) Figure 3: A circle packing approximation of a triply connected domain, its nerve, its completion to a triangulation of S2, and a combinatorially equivalent circle packing; (a)-(c) are from Oded's thesis; thanks to Andrey Mishchenko for creating (d) 6 8

2.3 Existence of Packings Oded applied the highest standards to his proofs and was not satisfied with "ugly" proofs. As we shall see, he found four (!) different new existence proofs for circle packings with prescribed combinatorics. Before discussing them, let us have a glance at previous proofs. The Circle Packing Theorem was first proved by Koebe [Ko2] in 1936. Koebe's proof of existence was based on his earlier result that every planar domain Ω with finitely many boundary components, say τη, can be mapped conformally onto a circle domain. A simple iterative algorithm, due to Koebe, provides an infinite sequence Ωη of domains conformally equivalent to Ω and such that Ωη converges to a circle domain. To obtain Ωη+ι from Ωη, just apply the Riemann mapping theorem to the simply connected domain (in С U {oo}) containing Ωη whose boundary corresponds to the (n mod m) — th boundary component of Ω. With the conformal equivalence of finitely connected domains and circle domains established, a circle packing realizing a given tangency pattern can be obtained as a limit of circle domains: Just construct a sequence of m-connected domains so that the boundary components approach each other according to the given tangency pattern. For instance, if the graph G = (V,E) is embedded in the plane by specifying simple curves 7e : [0,1] —> S2, e £ E, then the complement Ωε of the set |j7e[0,l/2-£]u(j7e[l/2 + £,l] is such an approximation. It is not hard to show that the (suitably normalized) conformally equivalent circle domains Ω^ converge to the desired circle packing when ε —> 0. Koebe's theorem was nearly forgotten. In the late 1970's, Thurston rediscovered the circle packing theorem as an interpretation of a result of Andreev [ΑΙ], [Α2] on convex polyhedra in hyperbolic space, and obtained uniqueness from Mostow's rigidity theorem. He suggested an algorithm to compute a circle packing (see [RSu]) and conjectured Theorem 2.3, which started the field of circle packing. Convergence of Thurston's algorithm was proved in [dVl]. Other existence proofs are based on a Perron family construction (see [Ste2]) and on a variational principle [dV2]. Oded's thesis [SI] was chiefly concerned with a generalization of the existence theorem to packings with prescribed convex shapes instead of discs, and to applications. A consequence ([SI], Proposition 8.1) of his "Monster packing theorem" is, roughly speaking, that the circle packing theorem still holds if discs are replaced by smooth convex sets. Theorem 2.4. ([SI], Proposition 8.1) For every triangulation G = (V,E) of the sphere, every a £ V, every choice of smooth strictly convex sets Dv for ν £ V \ {a}, and every smooth simple closed curve С, there is a packing Ρ = {Pv : ν £ V} with nerve G, such that Pa is the exterior of С and each Pv,v £ V \ {a} is positively homothetic to Dv. Sets A and В are positively homothetic if there is r > 0 and s £ С with A = rB + s. Strict convexity (instead of just convexity) was only used to rule out that three of the prescribed sets could meet in one point (after dilation and translation), and thus his packing theorem applied in much more generality. Oded's approach was topological in nature: Based on a cleverly constructed 7 9

Figure 4: A packing of convex shapes in a Jordan domain, from Oded's thesis spanning tree of (9, he constructed what he called a "monster". This refers to a certain \V dimensional space of configurations of sets homothetic to the given convex shapes, with tangencies according to the tree, and certain non-intersection properties. Existence of a packing was then obtained as a consequence of Brower's fixed point theorem. Here is a poetic description, quoted from his thesis: One can just see the terrible monster swinging its arms in sheer rage, the tentacles causing a frightful hiss, as they rub against each other. Applying Theorem 2.4 to the situation of Figure 3, with Dv chosen as circles when ν ^ {^1,^2,^3}, and arbitrary convex sets DVj, Oded adopted the Rodin-Sullivan convergence proof to obtain a new proof of the following generalization of Koebe's mapping theorem. The original proof of Courant, Manel and Shiftman [CMS] employed a very different (variational) method. Theorem 2.5. ([SI], Theorem 9.1; [CMS]) For every η + 1-connected domain Ω, every simply connected domain D С С and every choice of η convex sets Dj, there are sets Df- which are positively homothetic to Dj such that Ω is conformally equivalent to D\ VJ^D'-. Later [S7] he was able to dispose of the convexity assumption, and proved the packing theorem for smoothly bounded but otherwise arbitrary shapes. As a consequence, he was able to generalize Theorem 2.5 to arbitrary (not neccessarily convex) compact connected sets Dj, thus rediscovering a theorem due to Brandt [Br] and Harrington [Ha]. Oded then developed a differentiable approach to the circle packing theorem. In [S3] he shows Theorem 2.6. ([S3], Theorem 1.1) Let Ρ be a 3-dimensional convex polyhedron, and let Kcl3 be a smooth strictly convex body. Then there exists a convex polyhedron Q С Μ3 combinatorially equivalent to Ρ which midscribes K. Here UQ midscribes UT" means that all edges of Q are tangent to дК. Не also shows that the space of such Q is a six-dimensional smooth manifold, if the boundary of К is smooth and has 8 10

positive Gaussian curvature. For К = S , Theorem 2.6 has been stated by Koebe [Ko2] and proved by Thurston [T] using Andreev's theorem [Al], [A2]. Oded notes that Thurston's midscribability proof based on the circle packing theorem can be reversed, so that Theorem 2.6 yields a new proof of the Circle Packing Theorem (given a triangulation, just take К = S2, Q the midscribing convex polyhedron with the combinatorics of the packing, and for each vertex ν £ V, let Dv be the set of points on S2 that are visible from v). One defect of the continuity method in his thesis was that it did not provide a proof of uniqueness (see next section). In [S4] he presented a completely different approach to prove a far more general packing theorem, that had the added benefit of yielding uniqueness, too. A quote from [S4]: It is just about the most general packing theorem of this kind that one could hope for (it is more general than I have ever hoped for). A consequence of [S4] (Theorem 3.2 and Theorem 3.5) is Theorem 2.7. let G be a planar graph, and for each vertex ν £ V, let Tv be a proper 3-manifold of smooth topological disks in S2, with the property that the pattern of intersection of any two sets in Tv is topologically the pattern of intersection of two circles. Then there is a packing Ρ whose nerve is G and which satisfies Pv £ Tv for υ £ V. The requirement that Tv is a 3-manifold requires specification of a topology on the space of subsets of S2 : Say that subsets An С S2 converge to A if HmsupAn = liminf An = A and Ac = int(limsup A£). An example is obtained by taking a smooth strictly convex set К in R3 and letting Τ be the family of intersections И П дК, where Η is any (affine) half-space intersecting the interior of K. Specializing to К = S2, J- is the familiy of circles and the choice Tv — Τ for all ν reduces to the circle packing theorem. The proof of Theorem 2.7 is based on his incompatibility theorem, described in the next section. It provides uniqueness of the packing (given some normalization), which is key to proving existence, using continuity and topology (in particular invariance of domains). 2.4 Uniqueness of Packings I was always impressed by the flexibility of Oded's mind, in particular his ability to let go of a promising idea. If an idea did not yield a desired result, it did not take long for him to come up with a completely different, and in many cases more beautiful, approach. He once told me that if he did not make progress within three days of thinking about a problem, he would move on to different problems. Following Koebe and Schottky, uniqueness of finitely connected circle domains (up to Mobius images) is not hard to show, using the reflection principle: If two circle domains are conformally equivalent, the conformal map can be extended by reflection across each of the boundary circles, to obtain a conformal map between larger domains (that are still circle domains). Continuing in this fashion, one obtains a conformal map between complements of limit sets of reflection groups. As they are Cantor sets of area zero, the map extends to a conformal map of the whole sphere, hence is a Mobius transformation. Uniqueness of the (finite) circle packing can be proved in a similar 9 11

fashion. To date, the strongest rigidity result whose proof is based on this method is the following theorem of He and Schramm. See [Bo] for the related rigidity of Sierpinski carpets. Theorem 2.8 ([HS2], Theorem A). If Ω is a circle domain whose boundary has σ—finite length, then Ω is rigid (any conformal map to another circle domain is Mdhius). For finite packings, there are several technically simpler proofs. The shortest and most elementary of them is deferred to the end of this section, since I believe it has been discovered last. Rigidity of infinite packings lies deeper. The rigidity of the hexagonal packing, crucial in the proof of the Rodin-Sullivan theorem as elaborated in Section 2.6 below, was originally obtained from deep results of Sullivan's concerning hyperbolic geometry. He's thesis [He] gave a quantitative and simpler proof, still using the above reflection group arguments and the theory of quasiconformal maps. In one of his first papers [S2], Oded gave an elegant combinatorial proof that at the same time was more general: Theorem 2.9 ([S2], Theorem 1.1). let G he an infinite, planar triangulation and Ρ a circle packing on the sphere S2 with nerve G. If S2 \ carrier(P) is at most countable, then Ρ is rigid (any other circle packing with the same combinatorics is Mobius equivalent). The carrier of a packing {Dv : ν £ V(G)} is the union of the (closed) discs Dv and the "interstices" (bounded by three mutually touching circles) in the complement of the packing. The rigidity of the hexagonal packing follows immediately, since its carrier is the whole plane. The ingenious new tool is his Incompatibility Theorem, a combinatorial analog to the conformal modulus of a quadrilateral. To fully appreciate it, lets first look at its classical continuous counterpart, and defer the statement of the Theorem to Section 2.4.2 below. 2.4.1 Extremal length and the conformal modulus of a quadrilateral If you conformally map a 3xl-rectangle to a disc, such that the center maps to the center, what fraction of the circle does the image of one of the two short sides occupy? Despite having known the effect of "crowding" in numerical conformal mapping, I was surprised to learn of the numerical value of 0.0114... from Don Marshall (see [MS].) Of course, the precise value can be easily computed as an elliptic integral, but if asked for a rough guess, most answers are around 1/10 (the uniform measure with respect to length would give 1/8). Oded's answer, after a moments thought (during a tennis match in the early 90's), was 1/64, reasoning that this is the probability of a planar random walker to take each of his first three steps "to the right". An important classical conformal invariant, masterfully employed by Oded in many of his papers, is the modulus of a quadrilateral. Let Ω be a simply connected domain in the plane that is bounded by a simple closed curve, and let РьР2,Рз and p4 be four consecutive points on <9Ω. Then there is a unique Μ > 0 such that there is a conformal map / : Ω —> [0, Μ] χ [0,1] and such that / takes the pj to the four corners with f(p\) = 0 (by a classical theorem of Caratheodory, / extends homeomorphically to the boundary of the domains). There are several quite different instructive proofs of uniqueness of M. Each of the following three techniques has a counterpart in the circle packing world that has been employed by Oded. Suppose we are given two rectangles and a conformal map / between them taking corners to corners. 10 12

One method to prove uniqueness is to repeatedly reflect / across the sides of the rectangles. The resulting extention is a conformal map of the plane, hence linear, and it follows that the aspect ratio is unchanged. This is similar to the aforementioned Schottky group argument. A second method is to explicitly define a quantity λ depending on a configuration (Ω,ρι, ...,P4) in such a way that it is conformally invariant and such that one can compute λ for the rectangle [Ο,Μ] χ [0,1]. This is achieved by the extremal length of the family Γ of all rectifiable curves 7 joining two opposite "sides" [pl,p2] and [p3,p4] of Ω. The extremal length of a curve family Γ is defined as (nn% fpldzl)2 A(r)=sup ,l', , (1) ρ Jc pzdxdy where the supremum is over all "metrics" (measurable functions) ρ : С —> [0, oo). For the family of curves joining the horizontal sides in the rectangle [0, Μ] χ [0,1], it is not hard to show λ(Γ) = Μ. This simple idea is actually one of the most powerful tools of geometric function theory. See e.g. [Po2] or [GM] for references, properties and applications. Discrete versions of extremal length (or the "conformal modulus" l/λ) have been around since the work of Duffin [Duf]. In conformal geometry, they have been very succesfully employed beginning with the groundbreaking paper [Can]. Cannon's extremal length on a graph G = (V,E) is obtained from (1) by viewing non-negative functions ρ : V —> [0, oo) as metrics on (9, defining the length of a "curve" 7 С V as the sum Σν£-Ύ Ρ(ν)·> an<^ the "area" of ^ne graph as Σρ(.ν)2- See [CFP1] for an account of Cannon's discrete Riemann mapping theorem, and for instance the papers [HK] and [BK] concerning applications to quasiconformal geometry. Oded's applications to square packings and transboundary extremal length are briefly discussed in Section 2.7 below. A third and very different method is topological in nature and is one of the key ideas in [HS1]. Suppose we are given two rectangles Ω, Ω' with different aspect ratio and overlapping as in Fig. 5, and a conformal map / between them mapping corners to corners. Then the difference f(z) — ζ is ^0 on the boundary <9Ω. Traversing <9Ω in the positive direction, inspection of Fig. 5 shows that the image curve under f(z) — ζ winds around 0 in the negative direction. But a negative winding is impossible for analytic functions (by the argument principle, the winding number counts the number of preimages of 0). 2.4.2 The Incompatibility Theorem Again consider the overlapping rectangles Ω, Ω' of Fig. 5, and two combinatorially equivalent packings P, Pf whose nerves triangulate the rectangles, as in Fig. 6. Assume for simplicity that the sets Dv and Dfv of the packings are closed topological discs (except for the four sides Di, ...D4, D[,..., Df4 of the rectangles, which are considered to be sets of the packing). Intuitively, two topological discs D and Df are called incompatible if they intersect as in Fig. 5. More formally, say that D cuts Df if there are two points in Df \ interior(D) that cannot be connected by a curve in interior(Df \ D). Then Oded calls D and D' incompatible if D cuts D' or D' cuts D. As he notes, the motivation for the definition comes from the simple but very important observation that the possible patterns of intersection of two circles are very special, topologically. Indeed, any two circles are compatible. Theorem 2.10 ([S2], Theorem 3.1). There is a vertex υ for which Dv and Dfv are incompatible. 11 13

»l If» Figure 5: Conformally inequivalent rectangles; from (HS1). Γ4Ί ^ч r 4 # Figure 6: An incompatibility at the center.

Oded calls this result a combinatorial version of the modulus. However, it has rather little in common with the above notion of discrete modulus, except for the setup. Oded's clever proof by induction on the number of sets in the packing uses arguments from plane topology. An immediate consequence is that two rectangles cannot be packed by the same circle pattern, unless they have the same modulus Μ and hence are similar: if they could, just place the two packings on top of each other as in Fig. 6 and obtain two incompatible circles, a contradiction. In the same vein, it is not difficult to reduce the proof of the rigidity Theorem 2.9 to an application of the incompatibility theorem. 2.4.3 A simple uniqueness proof To end this section, here is a beautifully simple proof of the rigidity of finite circle packings whose nerve triangulates S2. I copied it from the wikipedia (search for circle packing theorem), and believe it is due to Oded. As before, stereographically project the packing to obtain a packing of discs in the plane. This time, assume that the north pole belongs to the complement of the discs, so that the planar packing will consist of three "outer" circles and the remaining circles contained in the interstice between them. "There is also a more elementary proof based on the maximum principle, which we now sketch. The key observation here is that if you look at the triangle formed by connecting the centers of three mutually tangent circles, then the angle formed at the center of one of the circles is monotone decreasing in its radius and monotone increasing in the two other radii. Consider two packings corresponding to G. First apply reflections and Mobius transformations to make the outer circles in these two packings correspond to each other and have the same radii. Next, consider a vertex ν where the ratio between the corresponding radius in the one packing and the corresponding radius in the other packing is maximized. Since the angle sum formed at the center of the corresponding circles is the same (360 degrees) in both packings, it follows from the above observation that the radius ratio is the same at all the neighbors of ν as well. Since G is connected, we conclude the radii in the two packings are the same, which proves uniqueness." 2.5 Koebe's Kreisnormierungsproblem Koebe's 1908 conjecture [Kol] that every planar domain can be mapped conformally onto a circle domain is still open, despite considerable effort by Koebe and others. Important contributions were made by Grotzsch, Strebel, Sibner and others. One difficulty is the aforementioned lack of uniqueness. Another problem is that Theorem 2.5 is not true in the infinitely connected case, as the following example from [S6] illustrates: If К = {χ + iy : χ = 0, ±1, ±^, ±|, ...,y £ [—1,1]}, and if D = C\UT, then there is no conformal map / of D, normalized by f(z) — z^Oasz^ oo, such that the component {iy : у £ [—1,1]} of dD corresponds to a horizontal line segment (or a point) while the other complementary components of f(D) are vertical line segments. The same example also illustrates the fundamental continuity problem: There is a circle domain Df conformally equivalent to D, but the boundary component corresponding to {iy : у £ [—1,1]} is just a point, so that the conformal map from Df to D cannot be extended to the boundary. The first joint paper of He and Schramm provided a breakthrough: 13 15

Theorem 2.11 ([HS1]). If Ω has at most countably many boundary components, then Ω is confor- mally equivalent to a circle domain Ω', and Ω' is unique up to Mobius transformation. Essentially, this result is still the strongest to date. Oded later [S6] gave a conceptually different and simpler proof based on his transboundary extremal length, which also applies to certain classes of domains with uncountably many boundary components. The proof in [HS1] used transfmite induction and was based on the topological concept of the fixed-point index. I will illustrate the beautiful idea by sketching their proof of uniqueness. As it turned out, this argument for uniqueness had been given earlier by Strebel [Str]. The simple but crucial idea is to use the following (see [HS1], Lemma 2.2): If / is a fixed-point free orientation preserving homeomorphism between two circles С and C/r, then the winding number of the curve f(z) — ζ, ζ £ С, around 0 is non-negative (recall Fig. 5 for a situation where the winding number is negative). Let / : Ω' —> Ω" be a conformal map and assume for simplicity that / extends continuously to the boundary (in case of finitely many boundary components this is immediate from the reflection principle, but in the countable case this step is non-trivial), and that / has no fixed points on the boundary. Composing with Mobius transformations, we may assume that oo G Ω' and that f{z) = ζ + a\/ζ + a^j'z2 + · · · . We want to show that / is the identity. If not, denote aj the first non-zero Taylor coefficient, then f(z) — ζ has winding number —j as ζ traverses a large circle \z\ = R, because f(z) — ζ behaves like a^z~K Moreover, each circular boundary component maps to a circular component. These boundary components are oriented negatively (to keep the domain to the left) and thus, by the above crucial idea, contribute a non-positive number to the winding of f(z) — ζ,ζ <Ε 0(Ω Π {\ζ\ < R} around 0. Hence the total winding number is negative, contradicting their generalization of the argument principle (the winding number counts the number of zeroes of f{z) — z.) Of course, I have swept most details under the rug, most notably the proof of continuity based on a powerful generalization of Schwarz' Lemma to circle domains (Theorem 0.6 in [HS1]). Combining the fixed-point index method of [HS1] with an analysis of quasiconformal deformations using the reflection group approach and Sullivan's rigidity theorems, He and Schramm [HS4] improve Theorem 2.11 to domains Ω for which all boundary components are circles or points except those in a countable and closed family. They also obtain the following generalization of the Riemann mapping theorem. Let А С С be simply connected. Theorem 2.12 ([HS4],[HS5]). If Ω С A is a relative circle domain (each connected component of Α\Ω is a point or a closed disc), then there is a relative circle domain Ω* in D conformally equivalent to Ω, and so that dA corresponds to <9D. Conversely, if Ω* is a relative circle domain in D; there is such Ω С А. The converse direction is the main result of [HS5]. 2.6 Convergence to conformal maps Let us return to the setting of the Rodin-Sullivan Theorem 2.3 about convergence of the discrete map fs to the conformal map /. Consider the piecewiese linear extension of fe from the carrier of Ρ to the carrier of P' that maps equilateral triangles to the corresponding triangles (formed by the centers of Pf). By the elementary "Ring Lemma" of [RSu], the angles of these triangles are 14 16

bounded away from 0 and π (so that fe is quasiconformal with dilation uniformly bounded above). At the heart of the Rodin-Sullivan proof is the uniqueness of the hexagonal packing as the only packing in the plane with nerve the triangular lattice (see the discussion in Section 2.4). It rather easily implies that tangent circles centered in a compact set of Ω correspond to tangent circles in D whose radii are asymptotically equal as ε —> 0. Hence the triangles in Pf are nearly equilaterals when ε is small (the angles tend to π/З), so that fe is nearly angle preserving in each triangle. Now the theory of quasiconformal maps readily yields equicontinuity of the family of maps /ε, and shows that every subsequential limit lim fe is a conformal map. The theorem follows from uniqueness of normalized conformal maps. He's thesis [He] provided a quantitative estimate for the rate of convergence of the angles (the difference to π/З is Ο {ε)). This estimate was known to imply convergence of the ratio of corresponding radii rad(Dr)/rad(D) to the absolute value \f'\ of the derivative. A probabilistic proof of C° (locally uniform) convergence of circle packings was given by Stephenson [Stel]. Convergence of fe to / for packings other than the hexagonal was proved in [HR], under the assumption of bounded valency of the graph. In [DHR], the quality of convergence was improved to convergence in C2 (that is, convergence of first and second derivatives; strictly speaking, instead of /ε they considered the "piecewise Mobius" map that sends interstices between triples of mutually tangent circles to the corresponding interstices). He and Schramm [HS6] found an elementary new convergence proof, based on the topological ideas discussed above and thus avoiding quasiconformal maps. Their proof also gave convergence up to C2, and worked in a more general setting. In particular, it does not need the assumption of uniformly bounded degree of [HR]. In the remarkable paper [HS8], He and Schramm proved C°°-convergence of hexagonal disk packings to the Riemann map: Theorem 2.13 ([HS8], Theorem 1.1). The discrete functions fe : Ve —> D converge in C°° to the Riemann mapping f : Ω —> D; in the sense that the discrete partial derivatives of fe of any order converge locally uniformly to the corresponding partial derivatives of f. The discrete first-order derivatives for ν £ V£ are de,kfe(v) = £-1(fe{v + £b>k)-fs(v)), where к £ 0,1, ...,5 and ω = (1 + iy/3)/2 is a 6—th root of unity. In particular, it follows that (^ε,ο)^Ζε converges to the A;—th derivative f(k' locally uniformly on G. The Schwarzian derivative S(f)(z)-n^-3-l^l (2) HJKZ> - f'(z) 2 f(zr (2) of a locally univalent analytic function measures the deviation of / from a Mobius transformation, in particular S(f) = 0 if / is Mobius. A key idea in the proof is to define a discrete analog of the Schwarzian derivative, to compute the (discrete) Laplacian of this Schwarzian, and to employ a regularity theorem for discrete elliptic equations to obtain boundedness of all partials of the Schwarzian. The definition of the discrete Schwarzian is the circle packing analog of an invariant that Oded so masterfully employed in his earlier work [S8] on circle patterns with the combinatorics of the square grid. 15 17

2.7 Other topics Oded's approach to both mathematics and to life was extraordinarily innovative and unaccepting of conventions. Notions that most people take for granted without even thinking about, he would open-mindedly question, often coming up with amazing alternative solutions. For example, I would not even think about camping on the foot of a glacier without a sleeping bag. Climbing little Tahoma peak with Oded, he proved to me that even this idea can be pursued. It was perhaps one of his less successful innovations, though. In the lovely paper [S5], Oded shows that for each triangulation G of a quadrilateral, there is a packing of a rectangle R by (horizontal) squares with the combinatorics of G (a square might degenerate to a point, as in Figure 7). (a) (b) Figure 7: A triangulation and the associated square packing. Thanks to David Wilson for providing this figure from [S5] The packing is actually a tiling: Indeed, Oded points out the following simple observation. Let Pa, Ръ, Pc be three rectangles whose edges are parallel to the coordinate axis. Suppose that the intersection of every two of these rectangles is nonempty. Then Pa Π Ръ Π Pc φ 0. The same tiling theorem was obtained independently by Cannon, Floyd and Parry in [CFP1]. Both employ Cannon's discrete extremal length (see Section 2.4.1) and obtain the side lengths s(v) of the squares as the weights p(v) of the extremal metric (corresponding to the family of "combinatorial curves" joining two opposite sides of the quadrilateral). It is quite different from the classical square packings of Brooks, Smith, Stone and Tutte [BSST], in particular, since the metrics considered here live on the vertices rather than the edges of the graph. A very similar idea is exploited in the important paper [S6]. The classical setting of extremal length (recall (1)) is a family Γ of curves contained in a domain Ω. Invariance λ(/(Γ)) = λ(Γ) 16 18

under conformal maps of Ω is almost trivial (just pull back metrics from /(Ω)). Oded's notion of transhoundary extremal length λ^(Γ) applies to curve families Γ that are not necessarily contained in Ω. The metrics are now replaced by generalized metrics ρ that, roughly speaking, also assign length to complementary components. The length J p\dz\ is replaced by J nnp\dz\ + ΣΡΡ(.Ρ) ^ 7 is not contained in Ω, where the sum is over all boundary components of Ω that 7 meets. Then the definition is λ^(Γ) = supp(inf7 J ηΩ p\dz\ + ^2pp(p))/ Jcp2dxdy1 and conformal invariance is again immediate. Using this innocent looking extension, Oded provides an elegant self-contained proof of the countable Koebe conjecture, and moreover is able to deal with the case of domains for which the complementary component satisfy a certain fatness condition (area(A Π B(x,r)) > cr2 for each component A, each χ £ A and each disc B(x,r) that does not contain A). Circle packings corresponding to infinite graphs G can be obtained by taking Hausdorff limits of packings corresponding to finite subgraphs, but where do they "live"? Beardon and Stephenson [BStl],[BSt2] have shown, under the assumption that the degrees of the vertices are uniformly bounded, that the carrier of such a packing is either the plane (call this case parabolic), or that it can be chosen to be the disc (hyperbolic). They also showed that both cases are mutually exclusive, and that the packing is hyperbolic if each degree is at least seven. The uniform boundedness assumption was later removed by He and Schramm [HS1], and they proved in general that the type of a packing is unique (that is, there is no infinite graph that packs both the disc and the plane). In the impressive paper [HS3], they characterize the type in terms of the discrete extremal length, and use it to show that the packing is parabolic if simple random walk on G is recurrent. They conclude (Theorem 10.1) that a packing is parabolic if at most finitely many vertices have degree greater than 6 (notice that every vertex of the hexagonal packing has degree 6). This paper contains their earlier result [HS3b] that a packing is hyperbolic if the lower average degree is greater than 6. By definition, the lower average degree is \av(G) = sup inf ——■ >^ deg(v). v J WqWdWo \W\ ^ bV ; 0 ' vew In the case that the degrees of the vertices are uniformly bounded, they also show that transience implies hyperbolicity. Jointly with Itai Benjamini, this line of investigation was carried further in [BS1] and [BS2], by applying circle- and square packings to constructions of harmonic functions on graphs. Another nice application of circle packings is the recurrence of (weak) limits of random planar graphs with bounded degree, [BS2]. I have always admired Oded's ability to find a good modification of a difficult problem that turns it into a tractable problem while keeping its essential features. One of the many examples is his work on discrete analytic function [S8]. Since circle packings can be viewed as discrete analogs of conformal maps, it is natural to ask for the analogs of analytic functions, thus giving up injectivity (disjointness of the discs). See [Ste2] for the state of the art and beautiful illustrations. Peter Doyle described collections of discs that are tangent according to the hexagonal pattern that are analogs of the exponential function. He conjectured that these would be the only "entire" circle packing immersions. While Oded was not able to resolve this conjecture, he did find that collections of overlapping discs based on the square grid seem better suited for the problem, and constructed the analog of the error function J e~z dz in this setting. Along the way, he introduced Mobius invariants that are discrete analogs of the Schwarzian derivative and became instrumental in his later work [HS8]. 17 19

(a) (b) Figure 8: The square grid and the \/iSG erf pattern, from [S8] 3 The Schramm-Loewner Evolution There are several excellent lecture notes, overview articles, and a textbook on SLE [La3], mostly by and for probabilists or theoretical physicists, see [BB3], [Car2], [Dup], [GK], [KN], [Sll], [Wl], [W2] and the references therein. It is not my intention to provide another streamlined introduction to the area. Instead, I would like to give a somewhat historic account with an emphasis on Oded's contributions, highlighting some of the mathematical challenges he faced. 3.1 Pre-history It is perhaps appropriate to very briefly describe the state of knowledge related to conformally invariant scaling limits prior to Oded's discovery of SLE, and to describe some of the results that were instrumental in his work. Oded's own historical narrative is Section 1.2 in [Sll]. Two-dimensional lattice processes such as the Self-Avoiding Walk (SAW), the Ising model, percolation, and diffusion limited aggregation (DLA), to name just a few, have been intensively studied by physicists and by probabilists for a long time. See Figure 21 for some pictures, and the aforementioned articles for descriptions of the models. In the physics community, many problems such as finding the HausdorlT dimension of scaling limits of these sets were considered well-understood. The implicit assumption of conformal invariance of the scaling limit allowed the use of the powerful machinery of conformal field theory and led to results such as Cardy's formula for the crossing probability of critical percolation [Carl]. On the mathematical side, progress was much slower, one of the hurdles being that in most cases the existence of a scaling limit was unknown. Even finding suitable definitions of the concept of scaling limit was a nontrivial task. In the late 1980's, Christian Pommerenke told me how compositions of (random) conformal maps onto slitted discs could be viewed as a variant of the Witten-Sander model for DLA [WS]. At the same time, Richard Rochberg and his son David were working on this setup. It seems that the only trace of this is a talk given by Rochberg at the March 1990 AMS Regional meeting in Manhattan, Kansas, titled "Stochastic Loewner Equation". Their model is similar to an approach 18 20

to Laplacian growth proposed by Hastings and Levitov [HL], and is quite different from what is now called Stochastic Loewner Evolution or Schramm-Loewner Evolution SLE. At that time, other analysts such as Lennart Carleson, Peter Jones and Nick Makarov worked with similar ideas, see e.g. [CM]. Oded was at best dimly aware of these activities, and was not really interested in stochastic processes such as DLA until much later. Greg Lawler's invention [La] of the Loop Erased Random Walk (LERW) provided the mathematics community with a process that shared some features with the Self-Avoiding Walk, but at the same time was more tractable, partly due to its Markovian property. Pemantle's work [?] and Wilson's algorithm provided a link between Uniform Spanning Trees (UST) and LERW's. Intensive research on the UST [Ly] culminated in the paper [BLPS] by Benjamini, Lyons, Peres and Schramm. The deep work of Rick Kenyon [Kel] combined powerful combinatorics and discrete complex analysis and exhibited conformal invariance properties of the LERW. He was also able to determine its expected length. 3.2 Definition of SLE Oded told me in 1997 about his idea to exploit conformal invariance in order to study the LERW. The streamlined way to present SLE in courses or texts, beginning with a crashcourse on the Loewner equation followed by a crash course on stochastic calculus (or the other way round) is, of course, not quite representative of its emergence. In a 2006 email exchange with Yuval Peres and myself about the history of SLE, Oded wrote: Up to the time when I started thinking about SLE, I did not really know what Loewner's equation was, or what was the idea behind it, though I did know that it was a tool which was important for the coefficients problem and that it involved slit mappings and a differentiation in the space of conformal maps. I kind of rediscovered it in the context of SLE and then made the connection. 3.2.1 The (radial) Loewner equation Loewner ([Lo]; see also [Dur],[Po2] or [La3]) introduced his differential equation as a tool in his attempt to prove the Bieberbach conjecture | β-η I ^ ^ concerning the Taylor coefficients of normalized conformal maps f(z) = ζ + Σ^=2 ап%п of the unit disc. It was also instrumental in the final solution by de Branges in 1984. Let 7 be a simple path that is contained in D except for one endpoint on <9D. More precisely, let 7 : [0, r] —> D be continuous and injective with 7(0) £ <9D and 7(4-) = 0, such that 7(0, г] С D. Denote Gt = О \ 7[0, t] so that Go = D. Then, for each 0 < t < r, there is a unique conformal map gt : Gt —> © that is normalized by gt(0) = 0 and gft(0) > 0. By Schwarz' Lemma, gft(0) strictly increases, #ό(0) = 1> an(i ^ ^s n°t nard to see that gft(0) —> 00 as t —> r. Hence we can reparametrize 7 so that τ = 00 and gft(0) = el. Loewner's theorem says that di9t{z) = φ)ο^φ) (3) for all £ > 0 and all ζ £ Gt, where the "driving term" (t = дгШ) Ξ 0Ώ 19 21

Figure 9: Conformal maps from slit discs onto discs» is continuous (a priori, gt is only defined in Gt, but it can be shown that gt extends to 7(t)). A simple but crucial observation is that the driving term ζτ of the curve ητ = дт{у) {more precisely, the parametrized curve 7T(s) ;— i)rr(7(X + s))) is given by £[ = ζτ+s* Thus "conformaily pulling down" a portion of 7 corresponds to shifting the driving term. Intuitively, one can think of the Loewner equation as describing a conformal map to a slitted disc as a composition of conformal maps onto infinitesimaliy siitted discs with slit at ζ*, plus the statement that the conformal map onto such a disc is z 1—* z + z^^At up to first order in Δί. Thus the Loewner equation associates with each simple curve 7 С В a continuous function Q with values in dB. Conversely, it is not hard to show that the solution gt(z) to the initial value problem (3), go{z) = z, forms a family of conformal maps of simply connected domains Gt onto D. In fact, Gt is the set of those points ζ e В for which the solution is well-defined on the interval [0, t]. It easily follows that Gt increases in t, and that z € Gt unless gs{z) ~ Cs f°r some s < t< The complement Kt = D \ Gt is called the hull of ζ. In our original setup of a slit disc, we simply recover the curve, Kt = 7(0, t]. It has been known since Kufarev [Ku] that smooth functions С generate smooth curves 7, but that there also exist continuous functions ζ for which the associated hull is not a simple arc in B. Kufarev's example simply is the computation that a circular chord 7 of the unit circle has continuous driving term. In fact, it can be topologically wild (not locally connected), see [MR]. My own interest in the Loewner equation originated when Oded asked me which driving terms generate curves. 20 22

3.2.2 The scaling limit of LERW The LERW is obtained from simple random walk by erasing loops chronologically. The main result Figure 10: A loop erased random walk in the disc, from [S9]. of Oded's celebrated paper [S9] was a conditional theorem: Assuming the existence and conformal invariance of the scaling limit of LERW, he showed that the Loewner driving term of the resulting (random) limiting curve is a Brownian motion on the unit circle, (t = elB<2t. To make this rigorous, he first gave the following definition of the notion of scaling limit: Let D С С be a domain, fix a £ D, and for δ > 0, consider the LERW on the graph δΊ? Π D, started at a point closest to a and stopped when reaching dD. Viewing the path of the LERW as a random subset of the sphere S2 = С U {oo}, its distribution is a discrete measure μ§ on the space of compact subsets of S2. Equipped with the Hausdorff distance, the space of compact subsets of S2 is a compact metric space, and so is the space of its Borel measures. The existence of subsequential weak limits μ = limj μ§ follows at once. If the limit measure μ = lim<5_>o βδ exists, it is called the scaling limit of LERW from atodD. Theorem 3.1 ([S9], Theorem 1.1). If each connected component of dD has positive diameter, then every subsequential scaling limit measure μ of the LERW from a to dD is supported on simple paths. In other words, the measure of the set of non-simple curves is zero. This theorem is interesting in its own right. It has been known previously that, loosely speaking and under mild assumptions, random curves have uniform continuity properties that imply their (subsequential) scaling limits to be supported on continuous curves [AB]. However, the fact that the loop erased paths are simple curves does not directly imply that the limiting objects have no loops. Indeed, the limits of other discrete random simple curves such as the critical percolation interface or the uniform spanning tree Peano path are not simple. The proof uses estimates for the probability distribution of "bottlenecks", based on harmonic measure estimates and Wilson's algorithm, and a topological characterization of simple curves. Next, Oded formulated the conjecture of existence and conformal invariance of the scaling limit as follows. 21 23

Conjecture ([S9],1.2) Let D ^ С be a simply connected domain in C; and let a £ D. Then the scaling limit of LERW from a to dD exists. Moreover, suppose that f : D —> D' is a conformal homeomorphism onto a domain Df С С. Then ί*μα,Ό — μ/(α),£>'> where μα,Ό is the scaling limit measure of LERW from a to dD, and μ/(α),Ό' ^s the scaling limit measure of LERW from f{a) to dD'. The most important and exciting result of [S9] was the insight that this conjecture implied an explicit construction of the limit in terms of the Loewner equation. By Theorem 3.1, the conjectural scaling limit μ induces a measure on the space of continuous real-valued functions (t via the correspondence 7 1—>■ ζ = e1^ of the Loewner equation. Oded showed that the law of ζ is that of a time-changed Brownian motion, B^t- Theorem 3.2 ([S9], Theorem 1.3). Assuming the above conjecture, the scaling limit μ is equal to the law of the hulls К associated with the driving term ζ = elB2t, where Bt,t > 0 is a Brownian motion started at a uniform random point in [0,2π). In his characteristic way, Oded pointed out the simple idea behind the theorem. From his paper: At the heart of the proof of Theorem 3.2 lies the following simple combinatorial fact about LERW. Conditioned on a subarc β' of the LERW β from 0 to dD, which extends from some point q £ β to dD, the distribution of β\β' is the same as that of LERW from 0 to d(D — β'), conditioned to hit q. When we take the scaling limit of this property, and apply the conformal map from D — β' to D; this translates into the Markov property and stationarity of the associated Lowner parameter c- He also notes that "the passage to the scaling limit is quite delicate". The translation into the Markov property and stationarity is by means of the aforementioned principle that "conformally pulling down" a portion 7' of 7 corresponds to shifting the driving term. Thus ζ" is a continuous process with stationary and independent increments. Now the theory of Levy processes (and the symmetry of LERW under reflection) implies that (t has the law of y^Bt for some к > 0 and a standard Brownian motion B. It remained to determine the constant к. То this end, Oded gives the following Definition. The (radial) stochastic Loewner evolution SLEK with parameter к > 0 is the random process of conformal maps gt generated by the Loewner equation driven by (t = ety^Bt. In Section 7 of [S9] he actually defined SLE as a process of random paths generated by the Loewner equation, and therefore had to restrict to those values of к for which the resulting hulls are simple curves; he conjectured that this is the interval [0,4]. Next, he analyzed the winding number of the SLE-path around 0, and of the LERW: If 6K(t) = arg7(£), t > 0, denotes the continuously defined argument along the curve, then he computed the variance E%(tf] = (K + o(l))\ogt. It follows that the winding number of the portion of the SLE path until its first hitting of the circle of radius ε centered at 0 has variance (к + o(l)) log(l/e). On the other hand, Kenyon's work [Ke2] implies that the variance of the winding number of LERW in D Π εΊ? is (2 + o(l)) log(l/e), and after some work the conclusion к = 2 follows. 22 24

Odcd went on to compute what he called the critical value for SLE: He proved that for к > 4, almost surely SLE will not generate simple paths, and conjectured that it will for к € [0,4]. See the discussion in Section 3.3.3 for the simple proof using Ito's formula (in the chordal case). However, Oiled was a self-taught newcomer to stocliastic calculus, discovered some of the basics himself, and commented on his proof in an email in January 1999: This must all be quite standard, to people with the right background. But not for me. 3.2.3 The chordal Loewner equation, percolation, and the UST The classical (radial) Loewner equation is well-suited for curves that join an interior point to a boundary point, such as curves generated by the LERW. Other processes generate curves joining two boundary points. Oiled realized how important the "correct'' normalizations arc in dealing with conformal maps and in particular the Loewner equation, and found the appropriate variant of the Loewner equation (it turned out later that this version lias been described earlier, beginning with N.V. Popova [Popl],[Pop2j; I would like to thank Alexander Vasilicv for this reference). He describes this in another email in January 1999: ,.· Figure 11: Percolation in a domain, from [Sll]. / have a mathematical querry. Before the question itself, here's the motivation. For the LERW scaling limit, the natural object is a probability measure on the set of paths from a point in the domain to the boundary. In other settings, the natural object is a probability measure joining two points on the boundary of a domain. Consider, for example, percolation in the unit disk. Let (f, 0) be a partition of the boundary of the disk to two arcs, disjoint except for the endpoints. Let К be the union of all percolation clusters inside the disk that are connected to f. Then the outer boundary of К is a path, a, joining the two endpoints off. The scaling limit of a is conjecturally conformally invariant (but not a simple path). Assuming conformal invariance, I'm optimistic that the scaling limit can be represented by a Loewner-Uke Broumian evolution. 77ie first step for this seems to be the following variation on Loewner's theorem: Thm: Let о : [0, oo) —· С 6c a continuous simple path such mat o(0) = 0, lim«-.oo o(f) = oo and Im(o(r)) > 0 when t > 0. Let ft be the conformal map from the upper half plane to the upper half 23 25

plane minus {o(s) : 0 < а < t), which is normalised by f,(z) = ζ + 0{\/z) near infinity. By change of parameterization of a (and perhaps changing its interval of definition), we may assume that f,{z) = z + t/z + 0{\)lz2 near infinity. Set g{w,t) = /,-'(«>)· Then {Og/Ot} = l/(g - *(/)), where k(t) = g{a(t),t). In the situation of percolation and related conformal mvariance models, one should expect k(t) = cBM(t), where BM is on the real line. Have you seen this theorem? The proof should not be difficult. It can either be derived from Loewner's theorem, or by adapting the proof. *» χ tf % V (») (b) Figure 12: The percolation exploration path In order to coincide with the normalization of the radial Locwncr equation, he later slightly adjusted the parametrizatioii of the path a so that Mz) = z + 2t/z + 0{l)/z2 and д ι ν 2 i.x т9М = дМ=щ- (4) With this normalization and assuming conformal invariancc of the percolation scaling limit, he showed that the (non-simple) limit curves would satisfy the chordal Locwncr equation (4) with Wt = y/GBt. The value 6 can be found as the only к such that the random sets generated by yfUBt satisfy Cardy's formula, or the locality property discussed below. This led to the definition of chordal SLEK as the random process of conformal maps g,:H\K,^H generated by the Locwner equation (4) with driving function W(t) = y/κΒι, where β is a standard Brownian motion. The hull Kt is the set of those points г for which g,(z) = Wm for some s < t so that (4) becomes undefined. Since gi is determined by Kt, one has the equivalent 24

Definition: Chordal SLEK is the process of random hulls (Kt,t > 0) generated by the Loewner equation (4) with Wt = \f^Bt. In the same paper, Oded also defines and analyzes subsequential scaling limits of the uniform spanning tree. He ends the paper by speculating (that is, stating without giving detailed proofs) about the Loewner driving term of the UST Peano curve in the upper half plane H. He finds that, again assuming existence and conformal invariance of the limit, this random space filling curve is SLE%. At the end of the introduction, he summarizes the findings of the paper as follows: The emerging picture is that different values of η in the differential equation (3) or (4) produce paths which are scaling limits of naturally defined processes, and that these paths can he space-filling, or simple paths, or neither, depending on the parameter к. Figure 13: The UST Peano curve, from [RoS]. 3.3 Properties and applications of SLE Two exciting developments took place shortly after the introduction of SLE, namely the very productive collaboration of Greg Lawler, Oded Schramm and Wendelin Werner, and the surprising proof of existence and conformal invariance of the percolation scaling limit by Stas Smirnov. I will begin describing the former, and defer the latter to Section 3.3.4. 3.3.1 Locality In the important papers [LW1] and [LW2], Lawler and Werner discovered that Brownian excursions have a certain restriction property (explained below), and that intersection exponents of conformally invariant processes with this property are closely related to those of Brownian motion. What was missing was a way to compute exponents of some conformally invariant process. Lawler, Schramm and Werner discovered that SLE provided such a process to which the universality arguments of Lawler and Werner [LW2] applied. The following email from Oded describes the crucial property: / don't remember if Fve mentioned to you the restriction property for SLE(6) that Greg, Wendelin and I have proved. It says that (up to time parameterization) the law of SLE(6) in an arbitrary 25 27

domain D starting from a point ρ on the boundary and stopped when it exits a small ball В around p, does not depend on the shape of the domain outside В (provided that D-B is connected, say). Thus, SLE(6) is purely a local process, like BM. This is not true for κ φ 6. For example, SLE(6) in the disk (with Loewner's original equation) is the same as SLE(6) in the half plane, with my variation on Loewner's equation. This seems to say that SLE(6) is a very special process. The above property is trivial for the discrete critical percolation exploration path, since the path can be grown "dynamically" by deciding the color of a hexagon only when the path meets it and needs to decide whether to turn "right" or "left". Hence, in light of the conjectured scaling limit, locality for chordal SLEq was not unexpected. The coincidence of chordal and radial SLEq, discussed below, was more surprising. Here is a precise statement of the locality property. Let D = Ш \ A be a simply connected subdomain of Ш1 such that A is bounded and also bounded away from 0. Denote дд the conformal map from D onto Ш1 with the hydrodynamic normalization (дл(^) — ζ —> 0 as ζ —> oo), and set Φ л — Яа — <м(0). Then SLE in D from 0 to oo is defined as the preimage of SLE in Ш1 from 0 to oo under Φ^4· The following expresses the fact that SLE in D is a time-change of SLE in H, up to the time that the process hits A. Let Τ = inf{i :КьпАфФ}ап.аТ = inf{i : Kt Π Φα(ΟΑ) φ 0}. Theorem 3.3 ([LSW2], Theorem 2.2). For η = 6, the processes (ΦΑ(Κ^,ί < Τ) and (Kt,t < f) have the same law, up to re-parametrization of time. The equivalence of chordal and radial SLEq was established in [LSW3], Theorem 4.1: Define the hulls Kt of chordal SLEK in D from 1 to —1 as the image of chordal SLEK in H, under the conformal map f(z) = (i — z)j[i + z). Thus Kt are hulls growing from 1 towards -1 in D. Denote Τ < oo the first time when Kt contains 0. Similarly, denote Kt the chordal SLEK hulls in D, started at 1, and denote Τ the first time when Kt contains —1. Then, for к = 6, the laws of (Kt,t < T) and (Kt,t < T) are the same, up to a random time change s = s(t). The proof and Girsanov's theorem also show that for all values of к, the laws of Kt and Ksu\ are equivalent (in the sense of absolute continuity of measures), if t and t are bounded away from Τ and T. See Proposition 4.2 in [LSW3]. The first proof of the locality Theorem 3.3 was rather long and technical, based on an analysis of the Loewner driving function of a curve under continuous deformation of the surrounding domain. A different and simpler proof was found later (see Proposition 5.1 in [LSW8]), by analyzing Wt := -I ht(Wt), where ht := gt ° дл ° Qt an<^ 9t — 9gt(D\Kt) is ^ne normalized conformal map of gt(D \ Kt) to Ш. Writing gt(z) = z + ^ + 0(\), ζ ζΔ computation shows that я ~ , ч dtat 2h't(Wt)2 OtQUz) = — = 4^. > Uz) - Wt ~gt(z) ~ Wt With Wt = \fcBt, computation using Ito's formula shows dWt = tit{Wt)dWt + ((/c/2) - i)til(Wt)dt. (5) Thus Wt is a local martingale if (and only if) к = 6, and a time change shows that (gt,t > 0) is SLEq. 26 28

3.3.2 Intersection exponents and dimensions The locality of SLEq has been used to determine the so-called intersection exponents of 2-dimensional Brownian motion, and to compute the Hausdorff dimensions of various sets associated with its trace. These results established Schramm's SLE and the Lawler-Werner universality arguments as a fundamental and powerful new tool. If B>\ and Bf are two independent planar Brownian motions started at two different points Bl φ Б2, it easily follows from the subadditivity of t i-> logP^O, t] Π B2[0, t] = 0] that there is a number ζ > 0 such that /i\C+o(i) Ρ^ΐΟ,ίΙίΊ^ΐΟ,ί] = 0] = f - Similarly, the half-plane exponent ζ of the event that two independent motions do not intersect and stay in a halfplane is given by /i\C+o(i) Ρ^ΐΟ,ίΙΠΰ^Ο,ί] = 0 and #*[(), ί] cM,j = 1,2] = ( - More generally, one considers exponents ζρ for the probability of the event that ρ independent motions are mutually disjoint, f(j, k) for the event that two packs of Brownian motions B1 U · · -UB^ and Bi+1 U · · · U B^+k are disjoint, and the corresponding half-plane exponents ζρ and ((j, k). So ζ = £(1,1). Also relevant is the disconnection exponent 2щ for the event that the union of j Brownian motions, started at 1, does not disconnect 0 from oo before time t. These and other intersection exponents have been studied intensively, and values such as ζ = 5/8 had been obtained by Duplantier and Kwon [DK] using the mathematically non-rigorous method of conformal field theory. An extension of C(j,k) for positive real к > 0 was given in [LW1], and some fundamental properties (in particular the "cascade relations") were established. In the series of papers [LSW2],[LSW3],[LSW5],[LSW7] (see [LSW1] for a guide and sketches of proofs), Lawler, Schramm and Werner were able to confirm the predictions, and they proved Theorem 3.4. For all integers j > 1 and all real numbers к > 0, (. , _ y/24j + 1 + V24fe + 1 - 2)2 - 4 _ 4n2 - 1 Uj,/Cj" 96 ' ζη" 48 ' >/. , ч _ V24j + 1 + V24fe + 1 - l)2 - 1 ~ _ 2n2 + n со,«j- 48 , u- 6 , and In particular, л 5-5 1 2 27 29

The proofs arc technical masterpieces combining a variety of different methods. Λ very rough description is as follows: First, half-plane intersection exponents of SLE% are computed, based on estimates for the crossing probability of (long) rectangles. This is done by establishing a version of Cardy's formula. Then, the universality ideas of [LVV2] are employed to pass from SLEk to Brownian motion. Finally, to cover the case к < 1, real analyticity of the exponent is shown by recognizing c-2^·*1 as the leading eigenvalue of an operator '/* on a space of functions on pairs of paths. For a fixed time t, the Brownian frontier is the boundary of the unbounded connected component of the complement of B[0, t), and the set of cut points is the set of those points ρ for which B[0, t)\{p) is disconnected. The set of pioneer points is the union of the frontiers over all t > 0. Mandelbrot [M] observed that the Brownian frontier looks like a long self-avoiding walk. Since the Hausdorff dimension of the self-avoiding walk was predicted by physicists to haw Hausdorff dimension 4/3, he conjectured that the Hausdorff dimension of the Brownian frontier is 4/3. Greg Lawlcr had shown in a series of papers (see [La2]) how the intersection exponents are related to the Hausdorff dimension of subsets of the Brownian path. He found the values 2 - 2<. 2 - %, ami 2 - »( for the dimension of tlie Brownian frontier, the set of cut points, ami the set of pioneer points. This actually required his stronger estimates of the intersection probabilitcs up to constant factors, rather than up to (l/0o(l). Simpler proofs of those estimates arc the content of [LSW6]. In combination with Theorem 3.4. this proved Mandelbrot's conjecture. Theorem 3.5 ([LSW3], [LSW7]). 7%e Hausdorff dimension of the frontier, the set of cut points, and the set of pioneer points of 2-dimensional Brownian motion is 4/3,3/4 and 7/4 almost surely. Figure 14: Λ Brownian path, with part of the frontier highl
{"ft_lang_label":"__label__en","ft_lang_prob":0.897629,"math_prob":0.9014908,"size":103993,"snap":"2019-43-2019-47","text_gpt3_token_len":27303,"char_repetition_ratio":0.1524969,"word_repetition_ratio":0.061828267,"special_character_ratio":0.24828595,"punctuation_ratio":0.14452787,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.97653335,"pos_list":[0,1,2],"im_url_duplicate_count":[null,1,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-10-21T03:51:58Z\",\"WARC-Record-ID\":\"<urn:uuid:f60e55a4-a3b7-4ab1-8f6e-427b3986cfe6>\",\"Content-Length\":\"147073\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:4f1064c8-b28f-4692-b583-8a6f3fb0ef62>\",\"WARC-Concurrent-To\":\"<urn:uuid:69004d18-7dcd-43b0-b756-b3bd197355e3>\",\"WARC-IP-Address\":\"179.43.147.124\",\"WARC-Target-URI\":\"https://el.b-ok.org/book/1315235/ac0d68\",\"WARC-Payload-Digest\":\"sha1:BXV233FUSFGAHGLKSIYOYJD7DZIEUTSD\",\"WARC-Block-Digest\":\"sha1:MIPD3AO6QVMG3BWCR4SDHIUUJZMB6447\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-43/CC-MAIN-2019-43_segments_1570987751039.81_warc_CC-MAIN-20191021020335-20191021043835-00260.warc.gz\"}"}