You are here

Combinatorics and Probability

Graham Brightwell, Imre Leader, Alex Scott, and Andrew Thomason, editors
Cambridge University Press
Publication Date: 
Number of Pages: 
[Reviewed by
Miklós Bóna
, on

This is a collection of 31 independent research papers presented at a conference to celebrate the 60th birthday of Béla Bollobás. See the table of contents for a full list of contributors and articles.

A collection of independent research articles is usually equal to the sum of its parts, but in this case, it is worth adding two remarks. First, the book starts with a very welcome biography of Bollobás written by Andrew Thomason. The facts and anecdotes told there were mostly new to this reviewer, a fellow Hungarian and fellow Combinatorialist. Second, this reviewer was very impressed, and even surprised, by the breadth of the articles of the collection. (Of course, the depth is impressive, too, but that is not surprising, given the pedigree of the contributors.)

The subjects of the articles in the volume contain, but are not limited to, Extremal Graph Theory, Game Theory, Spectral Graph Theory, Ramsey Theory, Hypergraphs, Quantum Computation, and even the Symmetric Group. Librarians at institutions with any research in Discrete Mathematics would do well in considering this book, since most combinatorialists are likely to find at least one paper interesting to them.

Miklós Bóna is Associate Professor of Mathematics at the University of Florida.

1. Measures of pseudorandomness for finite sequences: minimal values N. Alon, Y. Kohayakawa, C. Mauduit, and V. R. Rödl

2. MaxCut in H-Free graphs Noga Alon, Michael Krivelevich and Benny Sudakov

3. A tale of three couplings: Poisson–Dirichlet and GEM approximations for random permutations Richard Arratia, A. D. Barbour and Simon Tavaré

4. Positional games József Beck

5. Degree distribution of competition-induced preferential attachment graphs N. Berger, C. Borgs, J. T. Chayes, R. M. D’Souza and R. D. Kleinberg

6. On two conjectures on packing of graphs Béla Bollobás, Alexandr Kostochka and Kittikorn Nakprasit

7. Approximate counting and quantum computation M. Bordewich, M. Freedman, L. Lovász and D. Welsh

8. Absence of zeros for the chromatic polynomial on bounded degree graphs Christian Borgs

9. Duality in infinite graphs Henning Bruhn and Reinhard Diestel

10. Homomorphism-homogeneous relational structures Peter J. Cameron and Jaroslav Nešetřil

11. A spectral Turán theorem Fan Chung

12. Automorphism groups of metacirculant graphs of order a product of two distinct primes Edward Dobson

13. On the number of Hamiltonian cycles in a tournament Ehud Friedgut and Jeff Kahn

14. The game of JumbleG Alan Frieze, Michael Krivelevich, Oleg Pikhurko and Tibor Szabó

15. 2-Bases of quadruples Zoltán Füredi and Gyula O. H. Katona

16. On triple systems with independent neighbourhoods Zoltán Füredi, Oleg Pikhurko and Miklós Simonovits

17. Quasirandomness, counting and regularity for 3-uniform hypergraphs W. T. Gowers

18. Triangle-free hypergraphs Ervin Gyori

19. Odd independent transversals are odd Penny Haxell and Tibor Szabó

20. The first eigenvalue of random graphs Svante Janson

21. On the number of monochromatic solutions of x + y = z2 Ayman Khalfalah and Endre Szemerédi

22. Rapid Steiner symmetrization of most of a convex body and the slicing problem B. Klartag and V. Milman

23. A note on bipartite graphs wthout 2k-cycles Assaf Naor and Jacques Verstraëte

24. Book Ramsey numbers and quasi-randomness V. Nikiforov, C. C. Rousseau and R. H. Schelp

25. Homomorphism and dimension Patrice Ossona de Mendez and Pierre Rosenstiehl

26. The distance of a permutation from a subgroup of Sn Richard G.E. Pinch

27. On dimensions of a random solid diagram Boris Pittel

28. The small giant component in scale-free random graphs Oliver Riordan

29. A Dirac-type theorem for 3-uniform hypergraphs Vojtech Rödl, Andrzej Rucinski and Endre Szemerédi

30. On dependency graphs and the lattice gas Alexander D. Scott and Alan D. Sokal

31. Solving sparse random instances of max cut and max 2-CSP in linear expected time Alexander D. Scott and Gregory B. Sorkin.