Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica

by Sriram Pemmaraju, Steven Skiena
Cambridge University Press, Cambridge UK, 2003
494 pp., illus. 10 b/w. Trade, $60.00
ISBN: 0-521-80686-0.

Reviewed by Martha Patricia Niño Mojica
Pontificia Universidad Javeriana de Bogotá
Facultad de Artes Visuales
Colombia

ninom@javeriana.edu.co

This book is the definitive reference guide to Combinatorica——an extension of the popular computer software, Mathematica——with examples of the 450 combinatorics functions. The authors developed the newest version of this software that has dramatic improvements in graphical processing performance, representation, visualization, and many brand new functions. Steven Skiena has used Mathematica before the package was commercially released, and he had been working with Combinatorica for about 15 years. In 1990, he wrote the first book in the subject. Sriram Pemmaraju is Associate Professor of Computer Science at The University of Iowa, his main interests are combinatorics and graph theory, combinatorial optimization, approximation algorithms, and distributed algorithms.

Combinatorics is a branch of mathematics that studies counting. It analyses the possible combinations or permutations among numbers, and it is often related to statistics and probability. The first part of the book——from chapter one to four——has an introduction to Combinatorica and deals with permutations and combinations, algebraic combinatorics, partitions, compositions, and Young tableaux. The second part of the book——from chapter five to eight——is about graph theory, a subfield of mathematics that studies diagrams or graphs in order to determine relations among objects. Graphs serve as an interface between mathematics and computer science. The main topics are graph representation, generating graphs, properties of graphs such as traversals, connectivity, cycles in graphs, graph coloring, cliques, vertex cover and independent sets, algorithmic graph theory, shortest paths, minimum spanning trees, network flow, matching, partial orders, graph isomorphism, and planar graphs. It exhibits a wide variety of graphs, functions to generate them, invariants, and embeddings. It also shows the main classical problems such as flow, matching, Eurelian walks, Hamilitonian walks, vertex or edge coloring, and stable-dominant sets.

These two text’s sections are independent of each other, so it is possible to start in any of them. The book is also a good guide for writing your own programs with Mathematica. It is more than just a reference since it has all the necessary theory to comprehend the concepts. It does not have formal demonstrations but well explained practical thought, programming, and experimental exercises that provide a good flexibility for teaching a full semester class in this subject.

It is a very readable edition full of graphical and stimulating approaches to combinatorics and graph theories. The text is all about discover the excitement of mathematics. This is a great resource for the acknowledgement of beautiful patterns and important properties of graphs and other combinatorial objects. You can visualize these theories in order to identify iterations and make inferences. Since graphs are structures of points connected by lines, it shows how to generate fascinating constructions such as three dimensional butterfly graphs, stars, tree, hypercubes, dodecahedral, grids, and many other configurations. It is possible to animate interesting structures and transform these videos to animated GIF files for web pages. Combinatorica won the EDUCOM Higher Education Software Award and it is the most far-reaching software in the field of discrete mathematics. Animated examples and other useful information can be found at http://www.combinatorica.com/.

In regard to the application of applications of this field, the possibilities are endless: road networks, robot navigation, electronic circuits, artificial intelligence, evolutionary game theory, Internet mapping, social interactions among individuals, and even graphic design problems similar as the ones posed by the works of M.C. Escher in the field of combinatorial patterns that can be produced in an algorithmic. The book doesn’t cover specific Escher’s examples, but it is possible to find them online.

Curiosity is the main requisite for exploring this topic. This book is highly recommended. It is a well organized, and readable textbook for beginners and intermediate students. It is always advisable to have some mathematical savvy to get the most out of this text. You should not expect find all the aspects of Discrete Mathematics covered since the focus is in Combinatorics and Graph theory. Although the programs are not extremely long, it would be a good idea to supplement the book with a code repository of the practical exercises.