The University of Michigan Combinatorics Seminar
Winter 2011
January 21, 4:10-5:00, 3866 East Hall

Computing the partition function for perfect matchings in a hypergraph

Alexander Barvinok

University of Michigan


A k-uniform hypergraph is a collection of k-subsets, called edges, of a finite ground set of vertices. A matching in a hypergraph is a set of pairwise disjoint edges. A matching is called perfect if every vertex of the hypergraph belongs to some edge of the matching. It is an old and hopeless for k > 2 problem of interest to statistical physics to find out efficiently if there is a perfect matching in a given k-uniform hypergraph and how many perfect matchings are there. We introduce a certain partition function which generalizes the permanent of a matrix when k=2 and the graph is bipartite, obtain higher-dimensional versions of the van der Waerden and Bregman-Minc bounds for permanents and use the results to count perfect and nearly perfect matchings in hypergraphs. This is a joint work with A. Samorodnitsky (Hebrew University of Jerusalem).