Counting hypergraph matchings up to uniqueness threshold

DOI10.1016/j.ic.2019.02.001zbMath1423.05084OpenAlexW2962913771MaRDI QIDQ1740650

Yitong Yin, Jinman Zhao, Renjie Song

Publication date: 2 May 2019

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2019.02.001

zbMATH Keywords

Gibbs measureapproximate countingcorrelation decayhypergraph matchingsuniqueness threshold

Mathematics Subject Classification ID

Hypergraphs (05C65) Enumeration in graph theory (05C30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (2)

Smoothed counting of 0–1 points in polyhedra ⋮ Perfect sampling from spatial mixing

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of approximately counting in 2-spin systems on \(k\)-uniform bounded-degree hypergraphs
• Correlation decay and deterministic FPTAS for counting colorings of a graph
• Counting in two-spin models on \(d\)-regular graphs
• Ising models on locally tree-like graphs
• On the hardness of sampling independent sets beyond the tree threshold
• Markov random fields on an infinite tree
• Counting and sampling \(H\)-colourings
• Improved mixing condition on the grid for counting and sampling independent sets
• Spatial mixing and the connective constant: optimal bounds
• Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
• Theory of monomer-dimer systems
• Improved FPTAS for Multi-spin Systems
• Improved inapproximability results for counting independent sets in the hard-core model
• Counting independent sets up to the tree threshold
• Inapproximability for Antiferromagnetic Spin Systems in the Tree Nonuniqueness Region
• Approximate Counting of Matchings in (3,3)-Hypergraphs
• Approximating the Permanent
• Path coupling using stopping times and counting independent sets and colorings in hypergraphs
• FPTAS for Hardcore and Ising Models on Hypergraphs
• FPTAS for Weighted Fibonacci Gates and Its Applications
• Approximate Counting of Matchings in Sparse Uniform Hypergraphs
• Strong spatial mixing of list coloring of graphs
• FPTAS for Counting Monotone CNF
• Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
• A Simple FPTAS for Counting Edge Covers
• Combinatorial criteria for uniqueness of Gibbs measures
• Correlation Decay up to Uniqueness in Spin Systems
• Approximate Counting via Correlation Decay in Spin Systems

This page was built for publication: Counting hypergraph matchings up to uniqueness threshold