Combinatorics, Geometry and Probability
A Tribute to Paul Erdös

A panorama of combinatorics by the world's experts.

Béla Bollobás (Edited by), Andrew Thomason (Edited by)

9780521607667, Cambridge University Press

Paperback, published 19 August 2004

588 pages
24.6 x 19 x 3 cm, 1.058 kg

Paul Erdös was one of the greatest mathematicians of this century, known the world over for his brilliant ideas and stimulating questions. On the date of his 80th birthday a conference was held in his honour at Trinity College, Cambridge. Many leading combinatorialists attended. Their subsequent contributions are collected here. The areas represented range from set theory and geometry, through graph theory, group theory and combinatorial probability, to randomised algorithms and statistical physics. Erdös himself was able to give a survey of recent progress made on his favourite problems. Consequently this volume, consisting of in-depth studies at the frontier of research, provides a valuable panorama across the breadth of combinatorics as it is today.

1. Some unsolved problems Paul Erdös
2. Menger's theorem for a countable source set R. Aharoni and R. Diestel
3. On extremal set partitions in Cartesian product spaces R. Ahlswede and N. Cai
4. Matchings in lattice graphs and Hamming graphs M. Aigner and R. Klimmek
5. Reconstructing a graph from its neighbourhood lists M. Aigner and E. Triesch
6. Threshold functions for H-factors N. Alon and R. Yuster
7. A rate for the Erdös–Turán law A. D. Barbour and S. Tavaré
8. Deterministic graph games and a probabilistic intuition J. Beck
9. On oriented embedding of the binary tree into the hypercube S. L. Bezrukov
10. Potential theory on distance-regular graphs N. L. Biggs
11. On the length of the longest increasing subsequence in a random permutation B. Bollobás and S. Janson
12. On Richardson's model on the hypercube B. Bollobás and Y. Kohayakawa
13. Random permutations: some group-theoretic aspects P. J. Cameron and W. M. Kantor
14. Ramsey problems with bounded degree spread G. Chen and R. H. Schelp
15. Hamilton cycles in random regular digraphs C. Cooper, A. Frieze and M. Molloy
16. On triangle contact graphs H. de Fraysseix, P. Ossona de Mendez and P. Rosenstiehl
17. A combinatorial approach to complexity theory via ordinal hierarchies W. A. Deuber and W. Thumser
18. Lattice points of cut cones M. Deza and V. Grishukin
19. The growth of infinite graphs: boundedness and finite spreading R. Diestel and I. Leader
20. Amalgamated factorizations of complete graphs J. K. Dugdale and A. J. W. Hilton
21. Ramsey size linear graphs Paul Erdös, R. J. Faudree, C. C. Rousseau and R. H. Schelp
22. Turán–Ramsey theorems and Kp independence numbers Paul Erdös, A. Hajnal, M. Simonovits, V. T. Sós and E. Szemerédi
23. Nearly equal distances in the plane Paul Erdös, E. Makai and J. Pach
24. Clique partitions of chordal graphs Paul Erdös, E. T. Ordman and Y. Zalcstein
25. On intersecting chains in Boolean algebras Péter L. Erdös, A. Seress and L. A. Szekely
26. On the maximum number of triangles in wheel-free graphs Z. Füredi, M.X. Goemans and D. J. Kleitman
27. Blocking sets in SQS(2v) M. Gionfriddo, S. Milici and Zs. Tuza
28. (1,2)-factorisations of general Eulerian nearly regular graphs R. Häggkvist and A. Johansson
29. Oriented Hamilton cycles in digraphs R. Häggkvist and A. Thomason
30. Minimization problems for infinite n-connected graphs R. Halin
31. On universal threshold graphs P. L. Hammer and A. K. Kelmans
32. Image partition regularity of matrices N. Hindman and I. Leader
33. Extremal graph problems for graphs with a color-critical vertex C. Hundack, H. J. Prömel and A. Steger
34. A note on W1-to-W1 functions P. Komjáth
35. Topological cliques in graphs J. Komlós and E. Szemerédi
36. Local-global phenomena in graphs N. Linial
37. On random generation of the symmetric group T. Luczak and L. Pyber
38. On vertex-edge-critically n-connected graphs W. Mader
39. On a conjecture of Erdös and Cudakov A. R. D. Mathias
40. A random recolouring method for graphs and hypergraphs C. McDiarmid
41. Obstructions for the disk and the cylinder embedding extension problems B. Mohar
42. A Ramsey–type theorem in the plane J. Nesetril and P. Valtr
43. The enumeration of self-avoiding walks and domains on a lattice H. N. V. Temperley
44. An extension of Foster's network theorem P. Tetali
45. Randomised approximation in the Tutte plane D. J. A. Welsh
46. On crossing numbers, and some unsolved problems H. S. Wilf.

Subject Areas: Combinatorics & graph theory [PBV], Probability & statistics [PBT], Topology [PBP], Geometry [PBM]