Alexander Barvinok
University of Michigan
Title
Combinatorial counting, complex analysis and a bit of statistical physics
Abstract
A matching in a graph is a collection of edges such that every vertex is incident to at most one edge of the collection. Let v be the number of vertices of the graph and let d be the maximum degree of a vertex. It turns out that the number of all matchings in the graph, up to a relative error 0 < epsilon < 1, is determined by the number of matchings with k edges for k=O( sqrt{d} ln (v/epsilon)). We will discuss what the Koebe function has to do with it, and how this is related to the absence of a phase transition in monomer-dimer systems.
