You are here

Building Bridges: Between Mathematics and Computer Science

Martin Grötschel and Gyula O. H. Katona, editors
Publication Date: 
Number of Pages: 
Royal Society Mathematical Studies 19
[Reviewed by
Charles Ashbacher
, on

While the person well grounded in the applications of mathematics to computer science will recognize how the mathematics in this book relates to computing, that is not evident in the material. Most of the material deals with graph theory, which of course can be applied to the networking of computers. However, there are only a few times when any information explaining how the mathematics is applied to computing is included. The only paper where there is a direct link to computer science is “Combinatorial Problems in Chip Design”, on pages 333–368.

The level of the mathematics is fairly high, requiring some advanced background in many areas of graph theory, algebra, combinatorics, lattices, and other areas of discrete mathematics. There is a great deal of detail, with many theorems followed by detailed proofs. Particular areas of focus are in random and sparse graphs; graph invariants, the size and density of sumsets in a commutative group, binary vectors of low weight, the convergent sequences of dense graphs, random walks applied to the removal and re-shelving of library books and deformable polygons with near-mincuts.

While I have nothing negative to say about the material or the fact that it can be applied to computer science, the reality is that contrary to the title, there are few explicit bridges built between mathematics and computer science. Most are implied, with the knowledge for the implication the responsibility of the reader.

Charles Ashbacher splits his time between consulting with industry in projects involving math and computers, teaching college classes and co-editing The Journal of Recreational Mathematics. In his spare time, he reads about these things and helps his daughter in her lawn care business.

Preface Curriculum Vitae of L. Lovász.- Publications of László Lovász.- I. Bárány: On the Power of Linear Dependencies.- J. Beck: Surplus of Graphs and the Lovász Local Lemma.- A. Björner: RandomWalks, Arrangements, Cell Complexes, Greedoids, and Self-organizing Libraries.- A. Blokhuis and F. Mazzocca: The Finite Field Kakeya Problem.- B. Bollobás and V. Nikiforov: An Abstract Szemerédi Regularity Lemma.- U. Feige: Small Linear Dependencies for Binary Vectors of Low Weight.- A. A. Benczúr and M. X. Goemans: Deformable Polygon Representation and Near-Mincuts.- A. Schrijver: Graph Invariants in the Edge Model.- J. Nesetril and P. Ossona de Mendez: Structural Properties of Sparse Graphs.- K. Gyarmati, M. Matolcsi and I. Z. Ruzsa: Plünnecke's Inequality for Different Summands.- H. E. Scarf: The Structure of the Complex of Maximal Lattice Free Bodies for a Matrix of Size (n + 1) x n.- J. Solymosi: Incidences and the Spectra of Graphs.- J. Spencer: The Maturation of the Probabilistic Method.- V. Vu: A structural approach to subset-sum problems.