Disorder in Physical Systems Disorder in Physical Systems A volume in honour of John M. Hammersley on the occasion of his 70th birthday Edited by G.R. Grimmett and D.J.A. Welsh Preface On 21 March 1990 John Hammersley celebrates his seventieth birth- day. A number of his colleagues and friends wish to pay tribute on this occasion to a mathematician whose exceptional inventiveness has greatly enriched mathematical science. The breadthandversatilityofHammersley’sinterestsareremarkable, doublysoinanageofincreasedspecialisation. Inarangeofhighlyindivid- ual papers on a variety of topics, he has theorised, and posed (and solved) problems, thereby laying the foundations for many subjects currently un- derstudy. Byhis evidentloveformathematicsandanaffinityfor thehard problem, he has been an inspiration to many. If one must single out one particular area where Hammersley’s con- tribution has proved especially vital, it would probably be the study of random processes in space. He was a pioneer in this field of recognised importance, a field abounding in apparently simple questions whose res- olutions usually require new ideas and methods. This area is not just a mathematician’splayground,but isoffundamentalimportanceforthe un- derstanding of physical phenomena. The principal theme of this volume reflects various aspects of Hammersley’s work in the area, including disor- dered media, subadditivity, numerical methods, and the like. The authors of these papers join with those unable to contribute in wishing John Hammersley many further yearsof fruitful mathematical ac- tivity. August 1989 G.R. Grimmett D.J.A. Welsh Contents Contributors ix Speech Proposing the Toast to John Hammersley — 1 October 1987 1 David Kendall JakimovskiMethods and Almost-Sure Convergence 5 N.H. Bingham and U. Stadtmu¨ller Markov Random Fields in Statistics 19 Peter Clifford On Hammersley’s Method for One-Dimensional Covering Problems 33 Cyril Domb On a Problem of Straus 55 P. Erd˝os and A. S´ark¨ozy Directed Compact PercolationII: Nodal Points, Mass Distribution, and Scaling 67 J.W. Essam and D. Tanlakishani Critical Points, Large-Dimensionality Expansions, and the Ising Spin Glass 87 Michael E. Fisher and Rajiv R.P. Singh Bistability in Communication Networks 113 R.J. Gibbens, P.J. Hunt, and F.P. Kelly A Quantal Hypothesis for Hadrons and the Judging of Physical Numerology 129 I.J. Good Percolationin ∞+1 Dimensions 167 G.R. Grimmett and C.M. Newman Monte Carlo Methods Applied to Quantum-Mechanical Order-Disorder Phenomena in Crystals 191 D.C. Handscomb The Diffusion of Euclidean Shape 203 Wilfred S. Kendall Asymptotics in High Dimensions for Percolation 219 Harry Kesten viii Contents Some Random Collections of Finite Subsets 241 J.F.C. Kingman Probabilistic Analysis of Tree Search 249 C.J.H. McDiarmid Probability Densities for Some One-Dimensional Problems in Statistical Mechanics 261 J.S. Rowlinson Seedlings in the Theory of Shortest Paths 277 J. Michael Steele The Computational Complexity of Some Classical Problems from Statistical Physics 307 D.J.A. Welsh Lattice Animals: Rigorous Results and Wild Guesses 323 S.G. Whittington and C.E. Soteros Fields and Flows on Random Graphs 337 P. Whittle Bond PercolationCritical Probability Bounds for the Kagom´e Lattice by a Substitution Method 349 John C. Wierman Brownian Motion and the Riemann Zeta-Function 361 David Williams Index 373 Contributors N. H. BINGHAM, Department of Mathematics, Royal Holloway and Bedford New College, Egham Hill, Egham, Surrey TW20 0EX, UK. P. CLIFFORD, Mathematical Institute, University of Oxford, 24–29 St. Giles, Oxford OX1 3LB, UK. C. DOMB, Physics Department, Bar-Ilan University, Ramat-Gan, Israel. P. ERDO˝S, Mathematical Institute, Hungarian Academy of Sciences, Rea´ltanoda ul. 13–15, Budapest, Hungary. J. W. ESSAM, Department of Mathematics, Royal Holloway and Bedford New College, Egham Hill, Egham, Surrey TW20 0EX, UK. M. E. FISHER, Institute for Physical Science and Technology, The University of Maryland, College Park, Maryland 20742,USA. R. J. GIBBENS, Statistical Laboratory,University of Cambridge, 16 Mill Lane, Cambridge CB2 1SB, UK. I. J. GOOD, Department of Statistics, Virginia Polytechnic Institute and State University, Blacksburg,Virginia 24061,USA. G. R. GRIMMETT, School of Mathematics, University of Bristol, University Walk, Bristol BS8 1TW, UK. D. C. HANDSCOMB, Oxford University Computing Laboratory,8–11 Keble Road, Oxford OX1 3QD, UK. P. J. HUNT, Statistical Laboratory,University of Cambridge, 16 Mill Lane, Cambridge CB2 1SB, UK. F. P. KELLY, Statistical Laboratory,University of Cambridge, 16 Mill Lane, Cambridge CB2 1SB, UK. D. G. KENDALL, 37 Barrow Road, Cambridge CB2 2AR, UK. W. S. KENDALL, Department of Statistics, University of Warwick, Coventry CV4 7AL, UK. H. KESTEN, Department of Mathematics, Cornell University, Ithaca, New York 14853,USA. J. F. C. KINGMAN, Senate House, University of Bristol, Tyndall Avenue, Bristol BS8 1TH, UK. x Contributors C. J. H. MCDIARMID, Department of Statistics, University of Oxford, Oxford OX1 3TG, UK. C. M. NEWMAN, Department of Mathematics, University of Arizona, Tucson, Arizona 85721,USA. J. S. ROWLINSON, Physical Chemistry Laboratory,University of Oxford, South Parks Road, Oxford OX1 3QZ, UK. A. SA´RKO¨ZY, Mathematical Institute, Hungarian Academy of Sciences, Rea´ltanoda ul. 13–15, Budapest, Hungary. R. R. P. SINGH, AT&T Bell Laboratories, Murray Hill, New Jersey 07974,USA. C. E. SOTEROS, Department of Chemistry, University of Toronto, Toronto, Ontario M5S 1A1, Canada. U. STADTMU¨LLER, Universita¨t Ulm, Abteilung Mathematik-III, Oberer Eselsberg, 7900 Ulm, FRG. J. M. STEELE, Programin Statistics and Operations Research, School of Engineering and Applied Science, Princeton University, Princeton, New Jersey 08544,USA. D. TANLAKISHANI, Department of Mathematics, Royal Holloway and Bedford New College, Egham Hill, Egham, Surrey TW20 0EX, UK. D. J. A. WELSH, Merton College, Oxford OX1 4JD, UK. S. G. WHITTINGTON, Department of Chemistry, University of Toronto, Toronto, Ontario M5S 1A1, Canada. P. WHITTLE, Statistical Laboratory, University of Cambridge, 16 Mill Lane, Cambridge CB2 1SB, UK. J. C. WIERMAN, Department of Mathematical Sciences, The Johns Hopkins University, Baltimore, Maryland 21218, USA. D. WILLIAMS, Statistical Laboratory,University of Cambridge, 16 Mill Lane, Cambridge CB2 1SB, UK.