Combinatorics, Complexity, and Chance

Dominic Welsh has been the resident mathematician at Merton College, Oxford, for about 40 years, where he has guided and influenced generations of undergraduate and graduate students. Prior to his formal retirement in 2005, he was a Professor in the Mathematical Institute at Oxford University, where he served as Chairman for five years. Dominic Welsh is a leading figure worldwide in aspects of combinatorics and probability, including matroids, complexity, and percolation.Geoffrey Grimmett graduated under Dominic Welsh in 1971. He worked in Bristol University for 16 years before moving to Cambridge in 1992 as Professor of Mathematical Statistics. He is currently Head of the Department of Pure Mathematics and Mathematical Statistics, and a professorial fellow of Churchill College. His main interests lie in probability theory and rigorous statistical mechanics, and he is the author of successful texts on percolation theory and the random-cluster model.Colin McDiarmid gained his DPhil under Dominic Welsh in 1975. After a brief spell at the London School of Economics he became a fellow of Wolfson College, Oxford and then a fellow of Corpus Christi College. He is currently Professor of Combinatorics and Head of the Department of Statistics. His main interests lie in combinatorial theory, particularly in random structures and algorithms.

Dominic Welsh has made major contributions to the fields of combinatorics and discrete probability. This volume summarises and reviews the consistent themes from his work through a series of articles written by renowed experts. These articles contain original research work, set in a broader context by the inclusion of review material.

• Preface ; 1. Orbit counting and the Tutte polynomial ; 2. Eulerian and bipartite orientable matroids ; 3. Tutte-Whitney polynomials: some history and generalisations ; 4. A survey on the use of Markov chains to randomly sample colorings ; 5. Towards a matroid-minor structure theory ; 6. Random planar graphs with a fixed number of edges ; 7. Fourier analysis on finite Abelian groups: some graphical applications ; 8. Flows and ferromagnets ; 9. Approximating the Tutte polynomial ; 10. Non-separating circuits and cocircuits in matroids ; 11. Expanding the Tutte polynomial of a matroid over the independent sets ; 12. Connection matrices ; 13. Complexity of graph polynomials ; 14. Random planar graphs and the number of planar graphs ; 15. The contributions of Dominic Welsh to matroid theory ; 16. On the unknotting problem ; 17. Advances on the Erdos-Faber-Lovasz conjecture ; 18. Stochastic set-backs