Title Pages Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh Geoffrey Grimmett and Colin McDiarmid Print publication date: 2007 Print ISBN-13: 9780198571278 Published to Oxford Scholarship Online: September 2007 DOI: 10.1093/acprof:oso/9780198571278.001.0001 Title Pages (p.i) Oxford Lecture Series in Mathematics and its Applications (p.ii) OXFORD LECTURE SERIES IN MATHEMATICS AND ITS APPLICATIONS (p.iii) Combinatorics, Complexity, and Chance Series Editors John Ball Dominic Welsh 1. J. C. Baez (ed.): Knots and quantum gravity 2. I. Fonseca and W. Gangbo: Degree theory in analysis and applications 3. P. L. Lions: Mathematical topics in fluid mechanics, Vol. 1: Incompressible models 4. J. E. Beasley (ed.): Advances in linear and integer programming 5. L. W. Beineke and R. J. Wilson (eds): Graph connections: Relationships between graph theory and other areas of mathematics 6. I. Anderson: Combinatorial designs and tournaments 7. G. David and S. W. Semmes: Fractured fractals and broken dreams 8. Oliver Pretzel: Codes and algebraic curves 9. M. Karpinski and W. Rytter: Fast parallel algorithms for graph matching problems 10. P. L. Lions: Mathematical topics in fluid mechanics, Vol. 2: Compressible models 11. W. T. Tutte: Graph theory as I have known it 12. Andrea Braides and Anneliese Defranceschi: Homogenization of multiple integrals 13. Thierry Cazenave and Alain Haraux: An introduction to semilinear evolution equations Page 1 of 4 Title Pages 14. J. Y. Chemin: Perfect incompressible fluids 15. Giuseppe Buttazzo, Mariano Giaquinta and Stefan Hildebrandt: One- dimensional variational problems: an introduction 16. Alexander I. Bobenko and Ruedi Seiler: Discrete integrable geometry and physics 17. Doina Cioranescu and Patrizia Donato: An introduction to homogenization 18. E. J. Janse van Rensburg: The statistical mechanics of interacting walks, polygons, animals and vesicles 19. S. Kuksin: Hamiltonian partial differential equations 20. Alberto Bressan: Hyperbolic systems of conservation laws: The one- dimensional Cauchy problem 21. B. Perthame: Kinetic formulation of conservation laws 22. A. Braides: Gamma-convergence for beginners 23. Robert Leese and Stephen Hurley (eds): Methods and algorithms for radio channel assignment 24. Charles Semple and Mike Steel: Phylogenetics 25. Luigi Ambrosio and Paolo Tilli: Topics on analysis in metric spaces 26. Eduard Feireisl: Dynamics of viscous compressible fluids 27 Antonín Novotný and Ivan Straškraba: Introduction to the mathematical theory of compressible flow 28 Pavol Hell and Jaroslav Nešetřil: Graphs and homomorphisms 29 Pavel Etingof and Frederic Latour: The dynamical Yang–Baxter equation, representation theory, and quantum integrable systems 30 Jorge Ramirez Alfonsin: The diophantine Frobenius problem 31 Rolf Niedermeier: Invitation to fixed parameter algorithms 32 Jean-Yves Chemin, Benoit Desjardins, Isabelle Gallagher and Emmanuel Grenier: Mathematical geophysics: An introduction to rotating fluids and the Navier-Stokes equations 33 Juan Luis Vázquez: Smoothing and decay estimates for nonlinear diffusion equations 34 Geoffrey Grimmett and Colin McDiarmid: Combinatorics, complexity, and chance (p.iv) Great Clarendon Street, Oxford OX2 6DP Oxford University Press is a department of the University of Oxford. It furthers the University's objective of excellence in research, scholarship, Page 2 of 4 Title Pages and education by publishing worldwide in Oxford New York Auckland Cape Town Dar es Salaam Hong Kong Karachi Kuala Lumpur Madrid Melbourne Mexico City Nairobi New Delhi Shanghai Taipei Toronto With offices in Argentina Austria Brazil Chile Czech Republic France Greece Guatemala Hungary Italy Japan Poland Portugal Singapore South Korea Switzerland Thailand Turkey Ukraine Vietnam Oxford is a registered trade mark of Oxford University Press in the UK and in certain other countries Published in the United States by Oxford University Press Inc., New York ©Oxford University Press, 2007 The moral rights of the authors have been asserted Database right Oxford University Press (maker) First published 2007 All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, without the prior permission in writing of Oxford University Press, or as expressly permitted by law, or under terms agreed with the appropriate reprographics rights organization. Enquiries concerning reproduction outside the scope of the above should be sent to the Rights Department, Oxford University Press, at the address above You must not circulate this book in any other binding or cover and you must impose the same condition on any acquirer British Library Cataloguing in Publication Data Data available Library of Congress Cataloging in Publication Data Data available ISBN 0–19–857127–5 978–0–19–857127–8 1 3 5 7 9 10 8 6 4 2 Page 3 of 4 Illustration Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh Geoffrey Grimmett and Colin McDiarmid Print publication date: 2007 Print ISBN-13: 9780198571278 Published to Oxford Scholarship Online: September 2007 DOI: 10.1093/acprof:oso/9780198571278.001.0001 Illustration Dominic J. A. Welsh Page 1 of 1 PREFACE Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh Geoffrey Grimmett and Colin McDiarmid Print publication date: 2007 Print ISBN-13: 9780198571278 Published to Oxford Scholarship Online: September 2007 DOI: 10.1093/acprof:oso/9780198571278.001.0001 (p.v) PREFACE Dominic Welsh retired from Oxford University in 2005 having taught and inspired generations of mathematicians. His formal retirement was marked by a grand dinner in Merton College attended by many of his ex-undergraduate students, and by a research workshop (and dinner in Merton) attended by many of his ex-graduate students and some close colleagues. He has now resumed his combinatorial researches following this flurry of celebration. Dominic has been extremely influential in many aspects of Discrete Mathematics, especially in the theories of graphs, matroids, algorithmic complexity, cryptography, and knots, together with discrete physical models (including percolation) and swathes of applied probability. His doctoral thesis was written under the supervision of John Hammersley. It was the basis for the important publication entitled ‘First-passage percolation, subadditive processes, stochastic networks, and generalized renewal theory’, written jointly by Hammersley and Welsh in 1965. This classic paper laid the foundations for first-passage percolation and subadditive stochastic processes. The decade of the 1960s witnessed the emergence of Combinatorial Theory as a systematic topic of mathematics. In 1969, Dominic organized a ‘Conference on Combinatorial Mathematics and its Applications’ in Oxford, inviting an impressive list of diverse participants including Paul Erdő os and Roger Penrose. The now biennial British Combinatorial Conference was thus born, and it has remained one of the most important regular meetings in the subject worldwide. Page 1 of 2 PREFACE The publication in 1976 of Dominic's book ‘Matroid Theory’ was another important moment for Combinatorics. In this first major text on the subject, he made the case for this abstraction of linear independence as a powerful concept in Combinatorics. Percolation Theory and Matroid Theory are now well established and important topics in mathematics, and the authors (Grimmett and Oxley, respectively) of the current standard texts on these two subjects were each research students of Dominic. Dominic has written many fine research papers. His influence is recognized equally through his books, his questions, and his lectures and personal interactions. The books have broken new ground, and have invariably presented interesting material in an accessible and engaging way. The gift of asking the right question at the right moment is much esteemed by mathematicians, and Dominic has often hit the nail on the head, even if some of his conjectures have not stood the test of time. Dominic continues to travel extensively for mathematical visits and conferences. When looking for him at a research meeting, you must head for (p.vi) where the action is, where the discussions are most active and the excitementhighest. The topics represented in this volume reflect Dominic's wide vision of Combinatorics, and the contributors include some of his ex-graduate students together with several eminent colleagues. There are articles on graphs, matroids, polynomials, random structures, algorithms, and knots, under the theme ‘Combinatorics, Complexity, and Chance’. We trust that this volume will be a suitable tribute to an inspiring colleague, and we offer it to him with affection and appreciation. Bridget Welsh has kindly supplied the two photographs of Dominic. Geoffrey Grimmett Colin McDiarmid Page 2 of 2 LIST OF CONTRIBUTORS Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh Geoffrey Grimmett and Colin McDiarmid Print publication date: 2007 Print ISBN-13: 9780198571278 Published to Oxford Scholarship Online: September 2007 DOI: 10.1093/acprof:oso/9780198571278.001.0001 (p.ix) LIST OF CONTRIBUTORS (p.ix) LIST OF CONTRIBUTORS Peter J. Cameron, School of Mathematical Sciences, Queen Mary, University of London, Mile End Road, London E1 4NS, UK. Laura E. Chávez Lomelí, Department of Mathematics, Simon Fraser University, 8888 University Drive, Burnaby, British Columbia, V5A 1S6, Canada. Graham E. Farr, Clayton School of Information Technology, Monash University, Clayton, Victoria 3800, Australia. Alan Frieze, Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh PA 15213, USA. Jim Geelen, Department of Combinatorics and Optimization, University of Waterloo, 200 University Avenue West, Waterloo, Ontario, N2L 3G1, Canada. Bert Gerards, Centrum voor Wiskunde en Informatica, Kruislaan 413, 1098 SJ Amsterdam, The Netherlands. Stefanie Gerke, ETH Zürich, Institute of Theoretical Computer Science, CAB H 36.2, Universitätsstrasse 6, CH 8092 Zürich, Switzerland. Luis A. Goddyn, Department of Mathematics, Simon Fraser University, 8888 University Drive, Burnaby, British Columbia, V5A 1S6, Canada. Andrew Goodall, Department of Mathematics, University of Bristol, Bristol BS8 1TW, UK. Geoffrey Grimmett, Statistical Laboratory, Centre for Mathematical Sciences, University of Cambridge, Wilberforce Road, Cambridge CB3 0WB, UK. Page 1 of 3 LIST OF CONTRIBUTORS Mark Jerrum, School of Informatics, University of Edinburgh, The King's Buildings, Edinburgh EH9 3JZ, UK; School of Mathematical Sciences, Queen Mary, University of London, Mile End Road, London E1 4NS, UK. Bráulio Maia Junior, Departamento de Matemática e Estatística, Universidade Federal de Campina Grande, Campina Grande, Paraíba, 58105–305, Brazil. Koko Kalambay Kayibi, Design Research Group, Mathematics Research Centre, School of Mathematical Sciences, Queen Mary, University of London, Mile End Road, London E1 4NS, UK. Manoel Lemos, Departamento de Matemática, Universidade Federal de Pernambuco, Recife, Pernambuco, 50740–540, Brazil. (p.x) Lászlo Lovász, Microsoft Research, Redmond, WA 98052, USA; Department of Computer Science, Eötvös University, Pázmány Péter sétány 1/C, H-1117 Budapest, Hungary. Colin McDiarmid, Department of Statistics, Oxford University, 1 South Parks Road, Oxford OX1 3TG, UK. Tereza R. B. Melo, Departamento de Física e Matemática, Universidade Federal Rural de Pernambuco, Recife, Pernambuco, 52171–900, Brazil. Steven D. Noble, Department of Mathematical Sciences, Brunel University, Kingston Lane, Uxbridge UB8 3PH, UK. Marc Noy, Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Campus Nord, C. Jordi Girona 1–3, 08034 Barcelona, Spain. James Oxley, Department of Mathematics, Louisiana State University, Baton Rouge LA 70803–4918, USA. Jorge Ramírez Alfonsín, Université Pierre et Marie Curie, Paris 6, Equipe Combinatoire et Optimisation, 4 Place Jussieu, Paris 75252 Cedex 05, France. David Romero, Instituto de Matemáticas, Universidad Nacional Autónoma de México, 62210 Cuernavaca, Morelos, Mexico. Abdón Sánchez-Arroyo, Instituto Nacional de Estadística, Geografía e Informática, Héroe de Nacozari 2301, Puerta 3, Nivel 1, Aguascalientes, Ags., Mexico C.P. 20270. Angelika Steger, ETH Zürich, Institute of Theoretical Computer Science, CAB H 19.2, Universitätsstrasse 6, CH 8092 Zürich, Switzerland. David Stirzaker, St John's College, Oxford OX1 3JP, UK. Eric Vigoda, College of Computing, Georgia Institute of Technology, Atlanta GA 30332, USA. Page 2 of 3 LIST OF CONTRIBUTORS Andreas Weißl, ETH Zürich, Institute of Theoretical Computer Science, CAB H 24, Universitätsstrasse 6, CH 8092 Zürich, Switzerland. Geoff Whittle, School of Mathematics, Statistics and Computer Science, Victoria University, PO Box 600, Wellington, New Zealand. Page 3 of 3 ORBIT COUNTING AND THE TUTTE POLYNOMIAL Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh Geoffrey Grimmett and Colin McDiarmid Print publication date: 2007 Print ISBN-13: 9780198571278 Published to Oxford Scholarship Online: September 2007 DOI: 10.1093/acprof:oso/9780198571278.001.0001 ORBIT COUNTING AND THE TUTTE POLYNOMIAL Peter J. Cameron DOI:10.1093/acprof:oso/9780198571278.003.0001 Abstract and Keywords This chapter summarizes the various attempts to extend the Tutte polynomial of a matroid to a polynomial which counts orbits of a group on various sets of objects that the usual Tutte polynomial counts. In other words, the aim is to produce a hybrid of the Tutte polynomial and the cycle index polynomial. There have been various attempts at this, some of which are good for some aims but not for others. Keywords:   Tutte polynomial, matroid, orbit counting, cycle index polynomial, orbital chromatic polynomial, flow and tension polynomials This chapter is a summary (excluding some technical details), of various attempts by me and others to extend the Tutte polynomial of a matroid to a polynomial which counts orbits of a group on various sets of objects that the usual Tutte polynomial counts. Said otherwise, the aim is to produce a hybrid of the Tutte polynomial and the cycle index polynomial. There have been various attempts at this, each of which is good for some jobs but does not work for others. 1.1 Structure and symmetry A question that we meet in an elementary course on combinatorics or probability is: How many ways can we select n objects from a set of k objects? The answer depends on whether we are allowed to repeat objects in the sample, and whether we care about the order in which the selections are made. The well- known answers are given in the table. Page 1 of 12