Approximately counting independent sets in bipartite graphs via graph containers
From MaRDI portal
Publication:6074723
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
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