Computing the Partition Function for Perfect Matchings in a Hypergraph

DOI10.1017/S0963548311000435zbMath1234.05181arXiv1009.2397OpenAlexW2139974605MaRDI QIDQ3103630

Alex Samorodnitsky, Alexander I. Barvinok

Publication date: 8 December 2011

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1009.2397

zbMATH Keywords

nearly perfect matchings in hypergraphs

Mathematics Subject Classification ID

Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Computing the permanent of (some) complex matrices, Hafnians, perfect matchings and Gaussian matrices, Permanents of multidimensional matrices: Properties and applications, An efficient tree decomposition method for permanents and mixed discriminants, On testing Hamiltonicity of graphs, Approximating permanents and hafnians, Spectral Analysis of Matrix Scaling and Operator Scaling

Cites Work

• Exponentially many perfect matchings in cubic graphs
• The complexity of computing the permanent
• Positive diagonal scaling of a nonnegative tensor to one with prescribed slice sums
• The solution of van der Waerden's problem for permanents
• The number of \(t\)-wise balanced designs
• A short proof of Minc's conjecture
• Permanents of d-dimensional matrices
• Concentration of permanent estimators for certain large matrices.
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• Concentration of Random Determinants and Permanent Estimators
• New permanental upper bounds for nonnegative matrices
• New bounds on nearly perfect matchings in hypergraphs: Higher codegrees do help
• A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents