- Series
- ACO Colloquium
- Time
- Tuesday, February 27, 2018 - 11:00am for 1 hour (actually 50 minutes)
- Location
- Skiles 006
- Speaker
- Alexander Barvinok – University of Michigan – barvinok@umich.edu
- Organizer
- Prasad Tetali

Many hard problems of combinatorial counting can be encoded as problems
of computing an appropriate partition function. Formally speaking, such a
partition function is just a multivariate polynomial with great many
monomials enumerating combinatorial structures of interest. For example,
the permanent of an nxn matrix is a polynomial of degree n in n^2
variables with n! monomials enumerating perfect matchings in the
complete bipartite graph on n+n vertices. Typically, we are interested
to compute the value of such a polynomial at a real point; it turns out
that to do it efficiently, it is very helpful to understand the behavior
of complex zeros of the polynomial. This approach goes back to the
Lee-Yang theory of the critical temperature and phase transition in
statistical physics, but it is not identical to it: thinking of the
phase transition from the algorithmic point of view allows us greater
flexibility: roughly speaking, for computational purposes we can freely
operate with “complex temperatures”.
I plan to illustrate this approach on the problems of computing the
permanent and its versions for non-bipartite graphs (hafnian) and
hypergraphs, as well as for computing the graph homomorphism partition
function and its versions (partition functions with multiplicities and
tensor networks) that are responsible for a variety of problems on
graphs involving colorings, independent sets, Hamiltonian cycles, etc. (This is the first (overview) lecture; two more will follow up on Thursday 1:30pm, Friday 3pm of the week. These two lectures are each 80 minutes' long.)