The University of Michigan Combinatorics Seminar


Abstract 

A kuniform hypergraph is a collection of ksubsets, 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 kuniform 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 higherdimensional versions of the van der Waerden and BregmanMinc 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). 