Skip to main content
main-content

Über dieses Buch

Partition functions arise in combinatorics and related problems of statistical physics as they encode in a succinct way the combinatorial structure of complicated systems. The main focus of the book is on efficient ways to compute (approximate) various partition functions, such as permanents, hafnians and their higher-dimensional versions, graph and hypergraph matching polynomials, the independence polynomial of a graph and partition functions enumerating 0-1 and integer points in polyhedra, which allows one to make algorithmic advances in otherwise intractable problems.

The book unifies various, often quite recent, results scattered in the literature, concentrating on the three main approaches: scaling, interpolation and correlation decay. The prerequisites include moderate amounts of real and complex analysis and linear algebra, making the book accessible to advanced math and physics undergraduates.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Introduction

Abstract
What is a partition function? The answer depends on who you ask. You get one (multi)set of answers if you ask physicists, and another (multi)set if you ask mathematicians (we allow multisets, in case we want to account for the popularity of each answer).
Alexander Barvinok

Chapter 2. Preliminaries

Abstract
We assemble our toolbox from real and complex analysis. The main topics are inequalities inspired by convexity, polynomials with no roots in a particular domain and relations between convexity and restrictions on the location of the roots. We discuss the entropy of partitions, the Bethe-entropy, the Prékopa–Leindler inequality for integrals and the capacity of polynomials with non-negative real coefficients as a way to estimate a particular coefficient of a multivariate polynomial by solving a convex optimization problem.
Alexander Barvinok

Chapter 3. Permanents

Abstract
Introduced in 1812 by Binet and Cauchy, permanents are of interest to combinatorics, as they enumerate perfect matchings in bipartite graphs, to physics as they compute certain integrals and to computer science as they occupy a special place in the computational complexity hierarchy. This is our first example of a partition function and we demonstrate in detail how various approaches work. Connections with \({\mathbb {H}}\)-stable polynomials lead, in particular, to an elegant proof of the van der Waerden lower bound for the permanent of a doubly stochastic matrix. Combining it with the Bregman - Minc upper bound, we show that permanents of doubly stochastic matrices are strongly concentrated. Via matrix scaling, this leads to an efficient approximation of the permanent of non-negative matrices by a function with many convenient properties: it is easily computable, log-concave and generally amenable to analysis. As an application of the interpolation method, we show how to approximate permanents of a reasonably wide class of complex matrices and also obtain approximations of logarithms of permanents of positive matrices by low degree polynomials.
Alexander Barvinok

Chapter 4. Hafnians and Multidimensional Permanents

Abstract
We explore certain extensions of the permanent: hafnians enumerate perfect matchings in general graphs and multidimensional permanents enumerate perfect matchings in hypergraphs. With the notable exception of the mixed discriminant, which can be thought of as a “permanent-determinant” of a 3-dimensional array, these extensions no longer have connections to \(\mathbb H\)-stable polynomials, which is a major disadvantage. However, other methods we tried on permanents generally continue to work. Using scaling, we establish a decomposition of hafnians and multidimensional permanents into the product of an easy to handle “scaling part” and hard to handle “d-stochastic part”. We prove that the d-stochastic part is still concentrated, though weaker than in the case of the permanent.
Alexander Barvinok

Chapter 5. The Matching Polynomial

Abstract
Known in statistical physics as the partition function of the monomer-dimer model, the matching polynomial of a graph is an extension of the hafnian, as it enumerates all, not necessarily perfect, matchings in the graph. The Heilmann–Lieb Theorem asserts that the roots of the matching polynomial (with non-negative real weights on the edges) are negative real, which allows us to efficiently approximate the polynomial through interpolation anywhere away from the negative real axis. We demonstrate the “correlation decay” phenomenon of the probability for a random matching to contain a given vertex to be asymptotically independent on whether the matching contains some other remote vertex.
Alexander Barvinok

Chapter 6. The Independence Polynomial

Abstract
Known in statistical physics as the partition function of a hard core model, the independence polynomial of a graph is a far-reaching extension of the matching polynomial, demonstrating a much more complicated behavior.
Alexander Barvinok

Chapter 7. The Graph Homomorphism Partition Function

Abstract
Known in statistical physics as the partition function of a multi-spin system, this is one of the most general forms of a partition function.
Alexander Barvinok

Chapter 8. Partition Functions of Integer Flows

Abstract
We consider yet another extension of the permanent, and some of the methods and results of Chap. 3 (capacity of polynomials, connections to \(\mathbb {H}\)-stable polynomials, the van der Waerden and Bregman–Minc bounds) are used. Geometrically, with each integer point of a polyhedron in \({\mathbb R}^n\), we associate a monomial in n real variables and the partition function is just the sum of monomials over the integer points in the polyhedron.
Alexander Barvinok

Backmatter

Weitere Informationen

Premium Partner

    Bildnachweise