You are here

Discrete Structures and Their Interactions

Jason I. Brown
Chapman & Hall/CRC
Publication Date: 
Number of Pages: 
Discrete Mathematics and Its Applications
[Reviewed by
Miklós Bóna
, on

The book is a collection of examples, each of which shows either how discrete structures interact with each other, or how discrete structures interact with other parts of mathematics. An example of the former is a discussion of how hypergraphs connect with graph colorings, designs, Ramsey theory and partially ordered sets. An example of the latter is a series of theorems that relate graphs to linear algebra, topology, analysis, logic, and probability. A particularly interesting example is a proof of the Cayley-Hamilton theorem stating that every square matrix satisfies its own characteristic polynomial. The proof is interesting because it uses graphs to verify this algebraic result, and it does not contain any computations in the field over which the matrix is defined. Hence, the author says, the Cayley-Hamilton theorem holds not only algebraically, but also “formally”.

The book is meant for readers who have taken a course in discrete mathematics and so are familiar with most basic discrete structures, though not necessarily with all of them. Some of the structures that are less well-known for students but are covered in this book include simplicial complexes and multicomplexes. There probably a few researchers in discrete mathematics who are not familiar with the latter.

Given the book’s nature, it is not surprising that the text is broken up into short sections and subsections, often not longer than two pages. So the book will not be used for deep topical coverage, but it will provide a few good examples for many instructors of a discrete mathematics or combinatorics course. There are plenty of exercises, but only very few of them have a short answer included at the end. At the end of the book, we find six appendices, each about one part of mathematics whose connections with discrete math was covered in the book. There is also a list of eleven “Research Problems”. Perhaps “Directions of Research” would have been a better name for these because they are not specific questions, but indications of areas where it could be possible to use the methods discussed in the book to prove some stronger statements.

On the whole, I am certain I will use some examples I found in this book when I teach Combinatorics in the upcoming semester.

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

Computational Complexity

Discrete Structures—A Common Framework
Properties, Parameters and Operations
Representations and Models

Graphs and Directed Graphs
Graphs and Directed Graphs as Models
Graphs and Other Branches of Mathematics

Preorders and Partial Orders
Finite Topologies and Preorders
Representing Preorders and Partial Orders

Applying Hypergraphs
Modeling Hypergraphs

Complexes and Multicomplexes
Representations of Complexes and Multicomplexes
Applications of Complexes and Multicomplexes

Research Problems


Selected Solutions

Appendix A Set Theory
Appendix B Matrix Theory and Linear Algebra
Appendix C Abstract Algebra
Appendix D Probability
Appendix E Topology
Appendix F Logic