Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs

DOI10.1137/21M1466220MaRDI QIDQ5890038zbMATH OpenFDO

Authors Ewan Davies, Will Perkins

Publication date 28 April 2023

Published in SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

approximate countingcomputational thresholdFPRAShard-core modelindependent setssampling

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Cites work

• A fixed-parameter perspective on \#BIS
• A proof of the upper matching conjecture for large graphs
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Approximating the Permanent
• Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
• Central limit theorems from the roots of probability generating functions
• Central limit theorems, Lee-Yang zeros, and graph-counting polynomials
• Combinatorics and complexity of partition functions
• Correlation decay up to uniqueness in spin systems
• Counting in two-spin models on \(d\)-regular graphs
• Counting independent sets up to the tree threshold
• Decay of correlations for the hardcore model on the d-regular random graph
• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
• Extremal regular graphs: independent sets and graph homomorphisms
• Gibbs measures and phase transitions.
• scientific article; zbMATH DE number 3951995 (Why is no real title available?)
• Improved analysis of higher order random walks and applications
• Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models
• On a conjecture of Sokal concerning roots of the independence polynomial
• On a local limit theorem of the theory of probability
• On approximating the number of k-cliques in sublinear time
• On the average size of independent sets in triangle-free graphs
• On the complexity of fixed parameter clique and dominating set
• Optimal mixing of Glauber dynamics: entropy factorization via high-dimensional expansion
• Polynomial-Time Approximation Algorithms for the Ising Model
• Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction
• Spectral independence in high-dimensional expanders and applications to the hardcore model
• The complexity of counting colourings and independent sets in sparse graphs and hypergraphs
• The Complexity of Enumeration and Reliability Problems
• The maximum number of complete subgraphs in a graph with given maximum degree
• The relative complexity of approximate counting problems
• Tight bounds on the coefficients of partition functions via stability

Cited in

(6)

• Counting independent sets in graphs with bounded bipartite pathwidth
• Approximately counting independent sets of a given size in bounded-degree graphs
• Hypergraph independence polynomials with a zero close to the origin
• Fast and slow mixing of the Kawasaki dynamics on bounded-degree graphs
• Fast and slow mixing of the Kawasaki dynamics on bounded-degree graphs
• Parameter estimation for Gibbs distributions

This page was built for publication: Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs

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