Combinatorics and Complexity of Partition Functions

We can define a partition function of the family \(\mathcal F\) of subsets of \(\{1,2,\cdots ,n\}\) as \[p_{\mathcal F} (x_1,\cdots ,x_n)= \sum_{S\in \cal F} \prod_{i\in S} x_i .\]

Partition functions appear in combinatorics, physics and computer science, and their applications in these fields are quite different from each other. The book shows some of these applications and also it discusses methods to compute and approximate partition functions. A central application is computing the permanent of a matrix, which can then be used to find the number of perfect matchings of a graph. Multidimensional generalizations of this problem are also covered.

Partition functions are polynomials in several variables, so, as expected, polynomials that count parameters of graphs, such as the matching polynomial and the independence polynomial are included among the examples.

While the author has a friendly style and does not assume significant previous knowledge, the book does not contain any exercises. Here the author missed an opportunity to engage the reader, to show numerous additional applications of the theory, and to explain how it fits in the big picture. Therefore, the book will mostly be used as a reference material.

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