# Algebraic Combinatorics: Walks, Trees, Tableaux, and More

###### Richard P. Stanley
Publisher:
Springer
Publication Date:
2013
Number of Pages:
223
Format:
Hardcover
Series:
Undergraduate Texts in Mathematics
Price:
49.95
ISBN:
9781461469971
Category:
Textbook
BLL Rating:

The Basic Library List Committee strongly recommends this book for acquisition by undergraduate mathematics libraries.

[Reviewed by
Felipe Zaldivar
, on
12/14/2015
]

There are plenty of undergraduate books on graph theory and discrete mathematics in general. There are fewer books with an algebraic approach. If one adds as extra requisites that the book is well-written or elegant in its choice of topics, the field becomes even more rarified.

The book under review is one of those few exceptions. The chosen topics represent a sample of enumerative combinatorics suitable for the elementary algebra available to an undergraduate student. At the same time, this selection highlights the power of the algebraic method to obtain deep and interesting combinatorial results. The motivated student will be well prepared and willing to learn more algebra, even when her or his motivation lies in the combinatorial realm.

Perhaps a few samples will illustrate the book approach. In Chapter 1, page 1, we find the definition of a graph, its adjacency matrix, and loops in a graph. The first remark, on top of page 2 is that this adjacency matrix is real symmetric and its trace is the number of loops in the given graph. A nicely chosen example illustrates this remark. Next, we find the definition of a walk of length $\ell$ in a graph and immediately after the theorem that the $(i,j)$-entry in the $\ell$-th power of the adjacency matrix of a given graph is the number of walks of length $\ell$ from the $v_i$ vertex to the vertex $v_j$. The proof is just an interpretation of the formula for an entry in a product of matrices. The rest of this first chapter explores some consequences of the above theorem, essentially depending on the eigenvalues of the adjacency matrix.

A second sample is also classical: Pólya’s theory is introduced in Chapter 7. Here the problem is the enumeration of objects when the set of such objects is subject to the action of a finite group. Again, after some classical motivation using colorings of the combinatorial objects, Burnside’s lemma is proven and from it several consequences are obtained, including of course, Pólya’s theorem and one of its better known corollaries that count the number of colored necklaces of given length.

I could go on listing the combinatorial jewels in each chapter of this book, but let me just finish by saying that indeed, all the combinatorial topics have been chosen for the linear algebra and elementary group and field theory to shine and advertise their power. This is a book that can be used to teach a topics course for senior undergraduates. It will help them to solidify their just-acquired abstract algebra and at the same it will introduce them to some beautiful topics in pure or applied combinatorics.

Felipe Zaldivar is Professor of Mathematics at the Universidad Autonoma Metropolitana-I, in Mexico City. His e-mail address is fz@xanum.uam.mx.

Preface

Notation

1. Walks in graphs

2. Cubes and the Radon transform

3. Random walks

4. The Sperner property

5. Group actions on boolean algebras

6. Young diagrams and q-binomial coefficients

7. Enumeration under group action

8. A glimpse of Young tableaux

Appendix. The RSK algorithm

Appendix. Plane partitions

9. The Matrix–Tree Theorem

Appendix. Three elegant combinatorial proofs

10. Eulerian diagraphs and oriented trees

11. Cycles, bonds, and electrical networks

12. Miscellaneous gems of algebraic combinatorics

Hints

References