Portal de Periódicos da CAPES

Computing the Partition Function for Perfect Matchings in a Hypergraph

2011; Cambridge University Press; Volume: 20; Issue: 6 Linguagem: Inglês

10.1017/s0963548311000435

1469-2163

Alexander Barvinok, Alex Samorodnitsky,

Limits and Structures in Graph Theory

Given non-negative weights w S on the k -subsets S of a km -element set V , we consider the sum of the products w S 1 ⋅⋅⋅ w S m over all partitions V = S 1 ∪ ⋅⋅⋅ ∪ S m into pairwise disjoint k -subsets S i . When the weights w S are positive and within a constant factor of each other, fixed in advance, we present a simple polynomial-time algorithm to approximate the sum within a polynomial in m factor. In the process, we obtain higher-dimensional versions of the van der Waerden and Bregman–Minc bounds for permanents. We also discuss applications to counting of perfect and nearly perfect matchings in hypergraphs.