Computational Graph Theory with Combinatorica

Table of Contents Combinatorica in Action Combinatorica Resources The Old Combinatorica Errata list

We are proud to announce that Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica is finally available!

Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica is the definitive guide to Combinatorica, perhaps the most widely used software for teaching and research in discrete mathematics. The Combinatorica user community ranges from students to engineers to researchers in mathematics, computer science, physics, economics, and the humanities. Combinatorica has received the EDUCOM Higher Education Software Award and been employed in teaching from grade school to graduate levels. Combinatorica is included with every copy of the popular computer algebra system Mathematica.

Experimenting with Combinatorica provides an exciting new way to learn combinatorics and graph theory. This book provides examples of all 450 Combinatiorica functions in action, along with the associated mathematical and algorithmic theory. The book contains no formal proofs, but enough discussion to understand and appreciate all the algorithms and theorems contained within.

We cover classical and advanced topics on the most important combinatorial objects: permutations, subsets, partitions, and Young tableaux. We also cover all important areas of graph theory: graph construction operations, invariants, and embeddings as well as algorithmic graph theory.

This book can also serve as a unique textbook with enough material to teach or supplement full-semester, experimentally-enhanced courses in combinatorics and graph theory using Mathematica. Three interesting classes of exercises are provided -- theorem/proof, programming exercises, and experimental explorations, providing great flexibility in teaching and learning the material.


Combinatorica in Action!

Cycle cover of a hypercube
Hamiltonian cycle of the Dodecahedron
Bipartite matching of a grid graph
Min. spanning tree of 128 U.S. cities

The newest version of Combinatorica offers substantially improved efficiency and graphics. Thanks to our new sparse-graph representation, is now possible to do interesting operations on graphs with thousands or even hundreds of thousands of vertices. Additional functionality in terms of new graph invariants and computations have also been provided.

This new version was codeveloped by Sriram Pemmaraju and Steven Skiena. The new Combinatorica is best described in our book Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, Cambridge University Press, 2003. A nice review of our book appeared in the journal Leonardo.

The new Combinatorica is distributed with Mathematica starting with MMa version 4.2, but runs on older versions of MMa as well. The latest Combinatorica is available for download as the file NewCombinatorica.m. Let us know of your experiences. A short list of known bugs is available.

This work has been partially supported by the National Science Foundation and the Office of Naval Research.


Combinatorica Resources

Combinatorica resources include:

The official home of Combinatorica on the net is www.combinatorica.com, Send us bug reports or ask to be put on the mailing list for new releases. Other links of interest include:


Combinatorica: The Old Edition

The original version of Combinatorica was included with Mathematica versions 1.1 through 4.1 in the Packages/DiscreteMath directory. The on-line documentation for the original Combinatorica covers only a subset of these functions, which was best described in Steven Skiena's book:

Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, Advanced Book Division, Addison-Wesley, Redwood City CA, June 1990. ISBN number 0-201-50943-1. Japanese translation published by Toppan, Tokyo, July 1992. This book is now out of print, but might still be ordered on-line. The author still has a very small supply of copies which he may be induced to part with.

The old Combinatorica now runs (more or less) on Mathics! Check it out!

A Java-based graph editor for the old Combinatorica has been produced by Miguel Revilla. Look this page up in Google to enable translation from Spanish. The latest release of the package, data bases of interesting graphs, and additional files which may be of interest are available by anonymous FTP from ftp.cs.sunysb.edu.

Animations produced using Combinatorica by Joan Trias are also available.