2010/09/13 by Barvinok, Alexander, Samorodnitsky, Alex
#05A16 #05C30 #05C65 #15A15 #60C05 #82B20 #Combinatorics (math.CO) #FOS: Mathematics #FOS: Physical sciences #Mathematical Physics (math-ph) #Probability (math.PR)
paper · doi:10.48550/arxiv.1009.2397
Given non-negative weights wS on the k-subsets S of a km-element set V, we consider the sum of the products wS1 ... wSm for all partitions V = S1 cup ... cup Sm into pairwise disjoint k-subsets Si. When the weights wS are positive and within a constant factor, fixed in advance, of each other, 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.