On counting independent sets in sparse graphs
We prove two results concerning approximate counting of independent sets in graphs with constant maximum degree Delta. The first implies that the Markov chain Monte Carlo technique is likely to fail if Delta greater than or equal to 6. The second shows that no fully polynomial randomized approximation scheme can exist for Delta greater than or equal to 25, unless RP = NP.
primary 68q17 secondary 05c69 60j10 68e10 68q25 68w40