Algebraic combinatorics. (English) Zbl 0784.05001

Chapman and Hall Mathematics. New York: Chapman & Hall. xv, 362 p. (1993).
The book under review is an introduction to some of the interactions between algebra and combinatorics. The first half is devoted to the characteristic and matchings polynomials of a graph, and the second to polynomial spaces. But the book also includes many other topics closely connected with these main themes. The characteristic polynomial of a graph is the characteristic polynomial of its adjacency matrix. The matchings polynomial of a graph \(G\) is \(\mu(G)= \sum_{r\geq 0}(-1)^ r p(G,r)x^{n-2r}\), where \(p(G,r)\) is the number of \(r\)-matchings in \(G\), i.e., the number of subgraphs of \(G\) formed from \(r\) vertex-disjoint edges. These definitions suggest that the characteristic polynomial is an algebraic object and the matchings polynomial a combinatorial one. Despite this, these two polynomials are closely related and therefore they have been treated together. The reviewed book includes the following sections: 1. The matchings polynomial; 2. The characteristic polynomial; 3. Formal power series and generating functions; 4. Walk generating functions; 5. Quotients of graphs; 6. Matchings and walks; 7. Pfaffians; 8. Orthogonal polynomials; 9. Moment sequences; 10. Strongly regular graphs; 11. Distance-regular graphs; 12. Association schemes; 13. Representations of distance-regular graphs; 14. Polynomial spaces; 15. \(Q\)-polynomial spaces; 16. Tight designs. There are exercises and also notes and references in every chapter of the book. The prerequisites for successful digestion of the material offered are: 1. Basics of linear algebra. 2. Combinatorics: The basic language of graph theory, e.g. spanning trees, bipartite graphs and chromatic numbers; generating functions and formal power series. 3. Elementary group theory.


05-02 Research exposition (monographs, survey articles) pertaining to combinatorics
05E30 Association schemes, strongly regular graphs
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05A15 Exact enumeration problems, generating functions
05C15 Coloring of graphs and hypergraphs
05C12 Distance in graphs