Counting independent sets in unbalanced bipartite graphs

DOI10.1137/1.9781611975994.88MaRDI QIDQ5146865zbMATH OpenOpenAlexFDO

Authors Sarah Cannon, Will Perkins

Publication date 2 February 2021

Published in Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cited in

(19)

• Polymer dynamics via cliques: new conditions for approximations
• An FPTAS for the hardcore model on random regular bipartite graphs
• Zeros and approximations of holant polynomials on the complex plane
• Counting independent sets in graphs with bounded bipartite pathwidth
• Fast mixing via polymers for random graphs with unbounded degree
• Algorithms for \#BIS-hard problems on expander graphs
• Fast algorithms for general spin systems on bipartite expanders
• Independent sets in the hypercube revisited
• Efficient sampling and counting algorithms for the Potts model on ℤ^d at all temperatures
• Approximately counting independent sets in bipartite graphs via graph containers
• Homomorphisms from the torus
• Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs
• On the zeroes of hypergraph independence polynomials
• A refined graph container lemma and applications to the hard-core model on bipartite expanders
• A spectral approach to approximately counting independent sets in dense bipartite graphs
• Fast and perfect sampling of subgraphs and polymer systems
• A spectral independence view on hard spheres via block dynamics
• Pirogov-Sinai theory for the hard-core model beyond lattices
• Rapid mixing via coupling independence for spin systems with unbounded degree

This page was built for publication: Counting independent sets in unbalanced bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5146865)