Approximately counting independent sets in bipartite graphs via graph containers

DOI10.1002/rsa.21145zbMath1522.05210arXiv2109.03744MaRDI QIDQ6074723

Matthew Jenssen, Will Perkins, Aditya Potukuchi

Publication date: 12 October 2023

Published in: Random Structures & Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

independent setsapproximate counting\#BISgraph containers

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hypergraph containers
• Spectral algorithms for unique games
• Eigenvalue bounds for independent sets
• Cluster expansion for abstract polymer models
• On the number of graphs without 4-cycles
• On the ratio of optimal integral and fractional covers
• Two combinatorial covering theorems
• The relative complexity of approximate counting problems
• A proof of the upper matching conjecture for large graphs
• Algorithmic Pirogov-Sinai theory
• Independent sets in the middle two layers of Boolean lattice
• Faster exponential-time algorithms for approximately counting independent sets
• Counting independent sets in graphs
• Counting maximal antichains and independent sets
• Sampling 3-colourings of regular bipartite graphs
• Hoffman's ratio bound
• Fast mixing via polymers for random graphs with unbounded degree
• Counting independent sets up to the tree threshold
• Torpid Mixing of Local Markov Chains on 3-Colorings of the Discrete Torus
• FPTAS for #BIS with Degree Bounds on One Side
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• A Threshold Phenomenon for Random Independent Sets in the Discrete Hypercube
• How to Play Unique Games on Expanders
• Subexponential Algorithms for Unique Games and Related Problems
• Algorithms for #BIS-Hard Problems on Expander Graphs
• The Complexity of Ferromagnetic Ising with Local Fields
• Approximating the Partition Function of the Ferromagnetic Potts Model
• The Asymptotic Number of Lattices
• On the Shannon capacity of a graph
• Independent sets in the hypercube revisited
• Counting independent sets in unbalanced bipartite graphs
• Independent sets in hypergraphs
• Partitioning into Expanders
• Slow mixing of Glauber dynamics for the hard‐core model on regular bipartite graphs
• Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
• Counting Independent Sets and Colorings on Random Regular Bipartite Graphs
• Independent sets of a given size and structure in the hypercube
• Faster graph coloring in polynomial space
• Fast algorithms at low temperatures via Markov chains†

This page was built for publication: Approximately counting independent sets in bipartite graphs via graph containers