Encyclopaedia of Mathematical Sciences Volume no Probability Theory Subseries Editors: A.-S. Sznitman S.R.S. Varadhan Springer Berlin Heidelberg New York Hong Kong London Milan Paris Tokyo Harry Kesten (Editor) Probability on Discrete Structures ' Springer Harry Kesten Cornell University Department of Mathematics Malott Hall 310 14853-4201 Ithaca, NY USA e-mail: [email protected] Founding editor of the Encyclopaedia of Mathematical Sciences: R. V. Gamkrelidze Mathematics Subject Classification (2ooo): 6oB99, 6oCo5, 6oF17, 6oG5o, 60]10, 60]27, 6oK35 ISSN 0938-0396 ISBN 3-540-00845-4 Springer-Verlag Berlin Heidelberg New York This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilm or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer-Verlag. Violations are liable for prosecution under the German Copyright Law. Springer-Verlag Berlin Heidelberg New York a member of BertelsmannSpringer Science+ Business Media GmbH http://www.springer.de © Springer-Verlag Berlin Heidelberg 2004 Printed in Germany The use of general descriptive names, registered names, trademarks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant pro- tective laws and regulations and therefore free for general use. Typeset by LE-TEX )elonek, Schmidt & VBckler GbR, Leipzig Cover Design: E. Kirchner, Heidelberg, Germany Printed on acid-free paper 41/3142 db 54 3 2 1 o Preface Probability on discrete structures covers a wide area. Most probability prob lems involve random variables indexed by space and/or time. Almost always these problems have a version in which space and/or time are taken discrete. Roughly speaking this volume deals with some areas in which the discrete version is more natural than the continuous one, or perhaps even the only one which can be formulated without complicated constructions and machinery. Clear examples of this situation can be found in the articles in this volume on the random cluster model (by Grimmett) and on first-passage percolation (by Howard) and in most of the problems in the forthcoming book "Probability on Trees and Networks" by R. Lyons and Y. Peres. The article by Howard actually also discusses a continuous variant ~ called Euclidean first-passage percolation ~ but this came later and even though this continuous version has some clear advantages, its analysis brings in extra difficulties. Problems on discrete structures can often be stated with minimal prereq uisites, and sometimes only "elementary" (but by no means easy) probability theory is needed for their solution. Often the arguments have more of a com binatorial flavor than an analytic one, but the articles here certainly do not shun the use of the tools of analysis. Since the subject matter of this volume is so broad and varied, it is not surprising that it does not lend itself to a simple linear ordering. It did not seem possible to me to produce a volume which introduced a reader to much of the field in textbook fashion, in which one goes through the chapters in order. Instead, the present volume introduces a reader to the problems and progress so far, in various representative directions and subjects in which there is considerable activity, and which have seen recent successes. The various articles are not dependent on each other. There is one obvious omission from the list of possible topics in this vol ume, namely percolation. This subject was omitted here, because its classical aspects have been reviewed only two years ago by G. Grimmett in an ency clopedia article (see Development of Mathematics, 1950~2000, Jean-Paul Pier VI Preface ed.), while its very recent successes by Lawler, Schramm, Smirnov and Werner are still evolving while this volume is being prepared. I hope this volume will give a reader a solid introduction to the flavor and excitement of probability on discrete structures and encourage her to work in the subject herself. Ithaca, NY Harry Kesten July 25, 2003 Contents The Objective Method: Probabilistic Combinatorial Optimization and Local Weak Convergence David Aldous, J. Michael Steele. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 The Random-Cluster Model Geoffrey Grimmett . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 Models of First-Passage Percolation C. Douglas Howard ............................................... 125 Relaxation Times of Markov Chains in Statistical Mechanics and Combinatorial Structures Fabio Martinelli ................................................. 175 Random Walks on Finite Groups Laurent Saloff-Coste .............................................. 263 Index .......................................................... 347 List of Contributors David Aldous Fabio Martinelli Department of Statistics, Dipartimento di Matematica, University of California Berkeley, Universita' di Roma Tre, Berkeley, CA, 94720-3860. L.go S. Murialdo 1, [email protected] 00146 Roma, Italy. martin~at.uniroma3.it Geoffrey Grimmett Statistical Laboratory, Laurent Saloff-Coste University of Cambridge, Cornell University, Wilberforce Road, Department of Mathematics, Cambridge CB3 OWB, Ithaca, NY 14853-4201. United Kingdom. [email protected] g.r.grimmett@ statslab.cam.ac.uk J. Michael Steele Department of Statistics, C. Douglas Howard Wharton School, City University of New York, University of Pennsylvania, Baruch College. Philadelphia, PA 19104-6302. [email protected] [email protected] The Objective Method: Probabilistic Combinatorial Optimization and Local Weak Convergence David Aldous and J. Michael Steele 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1 A Motivating Example: the Assignment Problem . . . . . . . . . . . . . . . . . . . 3 1.2 A Stalking Horse: the Partial Matching Problem . . . . . . . . . . . . . . . . . . . . 4 1.3 Organization of the Survey . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2 Geometric Graphs and Local Weak Convergence. . . . . . . . . . . . . . 6 2.1 Geometric Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 g* as a Metric Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.3 Local Weak Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.4 The Standard Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.5 A Prototype: The Limit of Uniform Random Trees.................. 9 3 Maximal Weight Partial Matching on Random Trees .......... 12 3.1 Weighted Matchings of Graphs in General. . . . . . . . . . . . . . . . . . . . . . . . . 12 3.2 Our Case: Random Trees with Random Edge Weights . . . . . . . . . . . . . . . 12 3.3 Two Obvious Guesses: One Right, One Wrong . . . . . . . . . . . . . . . . . . . . . 12 3.4 Not Your Grandfather's Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.5 A Direct and Intuitive Plan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.6 Characterization of the Limit of B(T';."'all) . . . . . . . . . . . . . . . . . . . . . . . . 16 3.7 Characterization of the Limit of B(T~'9) • • • • • • • • • • • • • • • • • • • • • • • • • • 19 3.8 The Limit Theorem for Maximum Weight Partial Matchings .......... 21 3.9 Closing the Loop: Another Probabilistic Solution of a Fixed-Point Equation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.10 From Coupling to Stability~ Thence to Convergence . . . . . . . . . . . . . . . . 26 3.11 Looking Back: Perspective on a Case Study... . . . . . . . . . . . . . . . . . . . . . 28 4 The Mean-Field Model of Distance . . . . . . . . . . . . . . . . . . . . . . . . . . 29 4.1 From Poisson Points in !Rd to a Simple Distance Model . . . . . . . . . . . . . . 29 4.2 The Poisson Weighted Infinite Tree~ or, the PWIT . . . . . . . . . . . . . . . . . 31 4.3 The Cut-off Components of a Weighted Graph and a PWIT . . . . . . . . . . 32